SPFA 最短路算法求负环（POJ3259）多图负环

阳光穿透心脏的1/2处 2022-04-22 07:54 253阅读 0赞

# 什么是 SPFA #

## Bellman-ford的队列优化，即SPFA ##

1.  本质思想：每次从队列中取出一个点，利用这个点出发的所有边更新所有的终点距离，若更新成功，且被更新的点不在队列里，就把它放入队列。
2.  实现：队列初始只放第一个点，也是用一个dis数组，然后跑个不停。再用一个布尔数组记录一个点在不在队列里。
3.  若一个点入队了大于N次，则存在负环。
4.  一般不会用邻接矩阵写……但也可以用

![上传一张大佬图解][20181103164904568.gif]

上传一张大佬图解SPFA  
附上大佬博客链接： [SPFA][].

然后附上题目链接：[Wormholes][]

##### 题意：有 f 个农场，每个农场有 n 块地，其间有 m 条路，w条时光隧道，过去的时候时间会倒退 t 秒。判断是否可以从某块地出发后又回来，看到了离开之前的自己。 #####

##### 注意：前m条路为双向边，时空隧道为单向边。 #####

##### 方法：Floyd或者SPFA判断是否存在负权环。 #####

### AC代码 ###

#include <iostream>
    #include <cstring>
    #include <queue>
    #include <algorithm>
    #define inf 0x3f3f3f3f
    #define N 502 
    using namespace std;
    
    int n, m, w, Map[N][N];
    
    int dis[N];
    bool vis[N];
    
    bool spfa(int x){ 
    	///Shortest Path Faster Algorithm 
    	vis[x] = true;
    	dis[x] = 0;
    	int cnt[N] = { 0};
    	queue<int> q;
    	q.push(x);
    	
    	while(!q.empty()){ 
    		int t = q.front();
    		q.pop();
    		cnt[t]++;
    		if(cnt[t] > n) return true;
    		vis[t] = false;
    		for(int i = 1; i <= n; i++){ 
    			if(dis[i] > dis[t] + Map[t][i]){ 
    				dis[i] = dis[t] + Map[t][i];
    				if(!vis[i]){ 
    					vis[i] = true;
    					q.push(i);
    				}
    			}
    		}
    	}
    	return false;
    }
    
    void init(int n){ 
    	for(int i = 1; i <= n; i++)
    		for(int j = 1; j <= n; j++)
    		{ 
    			Map[i][j] = inf;
    		}
    	for(int i = 1; i <= n; i++){ 
    		dis[i] = inf;
    		vis[i] = false;
    	}
    }
    
    int main()
    { 
    	int u,v,w_;
    	int t;
    	ios::sync_with_stdio(false);
    	cin >> t;
    	while(t--){ 
    		cin >> n >> m >> w;
    		init(n);
    		for(int i = 0; i < m; i++){ 
    			cin >> u >> v >> w_;
    			if(Map[u][v] > w_)
    				Map[u][v] = Map[v][u] = w_;
    		}
    		for(int i = 0; i < w; i++){ 
    			cin >> u >>v >> w_;
    			Map[u][v] = -w_;
    		}
    		if(spfa(1)) cout << "YES" <<endl;
    		else cout << "NO" << endl;
    	}
    	return 0;
    }

#### 下面说一下我今天一上午做这道题遇到的问题 ####

1.  邻接矩阵大法好，因为要判断重边，邻接表不好判断重边
2.  出队列标记vis为未访问，进栈标记为访问
3.  疏松原理更新各个点到终点的距离
4.  最最坑的编译器问题，用了学校的电脑，被设置了某种权限，使测试结果与样例结果不符，让我一直怀疑人生 ，关爱生命，从使用自己电脑开始

**补充**

*  今天非常细心的紫紫问了我如果整张图不连通，是不是需要遍历所有节点做spfa，我一脸懵逼，然后她告诉我神奇的加虚节点操作，加入一个节点联通所有节点，建立权值为0的虚边。对当前虚节点进行spfa，若入队节点大于n+1则存在负环。

#include <iostream>
    #include <cstring>
    #include <queue>
    #include <algorithm>
    #define inf 0x3f3f3f3f
    #define N 502 
    using namespace std;
    
    int n, m, w, Map[N][N];
    
    int dis[N];
    bool vis[N];
    
    bool spfa(int x){ 
    	///Shortest Path Faster Algorithm 
    	vis[x] = true;
    	dis[x] = 0;
    	int cnt[N] = { 0};
    	queue<int> q;
    	q.push(x);
    	
    	while(!q.empty()){ 
    		int t = q.front();
    		q.pop();
    		cnt[t]++;
    		if(cnt[t] > n + 1) return true; // 修改为n+1
    		vis[t] = false;
    		for(int i = 1; i <= n; i++){ 
    			if(dis[i] > dis[t] + Map[t][i]){ 
    				dis[i] = dis[t] + Map[t][i];
    				if(!vis[i]){ 
    					vis[i] = true;
    					q.push(i);
    				}
    			}
    		}
    	}
    	return false;
    }
    
    void init(int n){ 
    	for(int i = 1; i <= n; i++)
    		for(int j = 1; j <= n; j++)
    		{ 
    			Map[i][j] = inf;
    		}
    	for(int i = 1; i <= n; i++){ 
    		dis[i] = inf;
    		vis[i] = false;
    	}
    }
    
    int main()
    { 
    	int u,v,w_;
    	int t;
    	ios::sync_with_stdio(false);
    	cin >> t;
    	while(t--){ 
    		cin >> n >> m >> w;
    		init(n);
    		for(int i = 0; i < m; i++){ 
    			cin >> u >> v >> w_;
    			if(Map[u][v] > w_)
    				Map[u][v] = Map[v][u] = w_;
    		}
    		for(int i = 0; i < w; i++){ 
    			cin >> u >>v >> w_;
    			Map[u][v] = -w_;
    		}
    		for(int i = 1; i <= n; i++){  //建立虚节点和虚边
    			Map[0][i] = 0;
    		} 
    		if(spfa(0)) cout << "YES" <<endl;
    		else cout << "NO" << endl;
    	}
    	return 0;
    }

[20181103164904568.gif]: /images/20220422/81fc0ece42e34947b5e340d3f8899a14.png
[SPFA]: http:/blog.csdn.net/rentenglong2012
[Wormholes]: http://poj.org/problem?id=3259