玄关疑问
查看原帖
玄关疑问
917025
XYzero楼主2024/8/24 11:55

rt,本蒟蒻写了一种 bfs bfs 的做法,大概就是枚举所有边看它能不能删除,然后统计数量,然后得分 70pts70pts ,想问思路哪里错了

代码如下:

#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;
} 
2024/8/24 11:55
加载中...