rt,本蒟蒻写了一种 bfs 的做法,大概就是枚举所有边看它能不能删除,然后统计数量,然后得分 70pts ,想问思路哪里错了
代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N = 3005;
int n,m,s1,s2,t1,t2;
struct Edge{
int v;
int id;
};
struct Node{
int x;
int step;
};
vector<Edge>e[N];
bool vis[N],Vis[N];
bool check(){
bool flg1 = false,flg2 = false;
memset(Vis,0,sizeof(Vis));
queue<Node>q;
q.push((Node){1,0});
Vis[1] = true;
while(!q.empty()){
Node now = q.front();
q.pop();
int u = now.x,st = now.step;
if(u == s1){
if(st <= t1)flg1 = true;
break;
}
for(auto to : e[u]){
int v = to.v,id = to.id;
if(vis[id] || Vis[v])continue;
q.push((Node){v,st + 1});
Vis[v] = true;
}
}
memset(Vis,0,sizeof(Vis));
queue<Node>q2;
q2.push((Node){1,0});
Vis[1] = true;
while(!q2.empty()){
Node now = q2.front();
q2.pop();
int u = now.x,st = now.step;
if(u == s2){
if(st <= t2)flg2 = true;
break;
}
for(auto to : e[u]){
int v = to.v,id = to.id;
if(vis[id] || Vis[v])continue;
q2.push((Node){v,st + 1});
Vis[v] = true;
}
}
return (flg1 && flg2);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= m;i++){
int x,y;
cin >> x >> y;
e[x].emplace_back((Edge){y,i});
e[y].emplace_back((Edge){x,i});
}
cin >> s1 >> t1 >> s2 >> t2;
if(!check()){
cout << "-1";
return 0;
}
int num = 0;
memset(vis,0,sizeof(vis));
for(int i = 1;i <= m;i++){
vis[i] = true;
if(check()){
num ++;
}
else vis[i] = false;
}
cout << num;
return 0;
}