洛谷 P3385 【模板】负环 (SPFA)

题意:有一个\(n\)个点的有向图,从\(1\)出发,问是否有负环.
题解:我们可以用SPFA来进行判断,在更新边的时候,同时更新路径的边数,因为假如有负环的话,SPFA这个过程一定会无限重复的遍历这个环,那么这个环中的边数也就会不断增加,因为我们只有\(n\)个点,所以假如某条路径的边数\(\ge n\)时,就说明有点重复使用了,也就说明一定存在负环.这题让我们从1开始走,所以只要对1初始化一下就行了.

代码:

struct misaka{

	int out;

	int val;

}e;

int t;

int n,m;

int dis[N];

bool st[N];

int cnt[N];

vector<misaka> v[N];

bool spfa(){

	queue<int> q;

	st[1]=true;

	dis[1]=0;

	q.push(1);

	while(!q.empty()){

		int node=q.front();

		q.pop();

		st[node]=false;

		for(auto w:v[node]){

			int now=w.out;

			if(dis[now]>dis[node]+w.val){

				dis[now]=dis[node]+w.val;

				cnt[now]=cnt[node]+1;

				if(cnt[now]>=n) return true;

				if(!st[now]){

					st[now]=true;

					q.push(now);

				}

			}

		}

	}

	return false;

}

int main() {

    //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	scanf("%d",&t);

	while(t--){

		scanf("%d %d",&n,&m);

		for(int i=1;i<=n;++i){

			dis[i]=INF;

			st[i]=false;

			cnt[i]=0;

		}

		for(int i=1;i<=m;++i){

			int a,b,val;

			scanf("%d %d %d",&a,&b,&val);

			if(val>=0){

				v[a].pb({b,val});

				v[b].pb({a,val});

			}

			else

			v[a].pb({b,val});

		}

		if(spfa()) puts("YES");

		else puts("NO");

		for(int i=1;i<=n;++i){

			v[i].clear();

		}

	}

    return 0;

}

巴特西

洛谷 P3385 【模板】负环 (SPFA)

最新文章

热门文章