本文主要是介绍poj 3259 spfa判断回路。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
每个点松弛>=n的话，则说明存在回路。（n为顶点数目。）
附代码：
#include <iostream>
#include <queue>
using namespace std;
int map[1001][1001];
int n,m,w;
const int maxn=1111111111;
bool spfa(int s)
{queue<int>que;int d[1001],c[1001]; //c[]是用来记录松弛了多少次。bool used[1001];for(int i=1;i<=n;i++)d[i]=maxn;memset(c,0,sizeof(c));memset(used,0,sizeof(used));que.push(s);d[s]=0;used[s]=1;c[s]++; //松弛一次;+1while(!que.empty()){int id=que.front();que.pop();used[id]=0; //if(++c[id]>=n) return 1也可以放在这里 则不需要代码的c[s]++;for(int i=1;i<=n;i++)if(d[i]>d[id]+map[id][i]) {d[i]=d[id]+map[id][i]; if(!used[i]){if(++c[i]>=n) //松弛一次+1 判断。return 1;used[i]=1;que.push(i);}}}return 0;
}
int main()
{int cas;cin>>cas;while(cas--){cin>>n>>m>>w;for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)map[i][j]=maxn;while(m--){int a,b,c;cin>>a>>b>>c;if(map[a][b]>c)map[a][b]=map[b][a]=c;}while(w--){int a,b,c;cin>>a>>b>>c;map[a][b]=-c;}if(spfa(1))cout<<"YES\n";elsecout<<"NO\n";}return 0;
}简化的代码，不过慢了将近一倍：
#include "stdafx.h"
#include <iostream>
#include <queue>
using namespace std;
int map[1001][1001];
int n,m,w;
const int maxn=1111111111;
bool spfa(int s)
{queue<int>que;int d[1001];for(int i=1;i<=n;i++)d[i]=maxn;que.push(s);d[s]=0;int cnt=0;while(!que.empty()){if(cnt++>n*n)return 1; //判断总的松弛数，如果大于n*n(点的数量),则有负环。但是效率太慢int id=que.front();que.pop();for(int i=1;i<=n;i++)if(d[i]>d[id]+map[id][i]){d[i]=d[id]+map[id][i];que.push(i);}}return 0;
}
int main()
{int cas;cin>>cas;while(cas--){cin>>n>>m>>w;for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)map[i][j]=maxn;while(m--){int a,b,c;cin>>a>>b>>c;if(map[a][b]>c)map[a][b]=map[b][a]=c;}while(w--){int a,b,c;cin>>a>>b>>c;map[a][b]=-c;}if(spfa(1))cout<<"YES\n";elsecout<<"NO\n";}return 0;
}这篇关于poj 3259 spfa判断回路。的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
