图论——负环以及玄学优化
负环的定义
一个图中存在一个环，里面包含的边的边权总和<0 。在含有负环的图，是无法求出最短路的，因为只要是重复走这个环，最短路就会不断缩小。
负环的求法
基于Bellman-Ford算法
若n次迭代，算法仍旧未结束，则图中存在负环，反正咋不存在负环。
基于SPFA算法。
1.统计每个点入队的次数，如果某个点入队n次（也可以大于），说明存在负环。
2.统计当前每个点的最短路所包含的边数，如果某点的最短路包含的边数>=n，说明存在负环。
关于算法2，进阶指南的解释如下：
根据抽屉原理，如果某点的最短路包含的边数>=n,那么这条最短路必然重复经过某个点p，即最短路上存在一个环使得环上各点都能更新下一点的dis值，最短路的长度越来越短，无法结束算法。
玄学优化
1.当所有点的入队次数超过2n时，我们就认为图中很大可能存在负环。
2.可以把队列换为堆。
3.把SPFA基于BFS改为基于DFS
题目：
题意：
给定一个无向图，问是否存在负环。
思路：
用SPFA判断每个点入队的次数，要注意有多组测试数据，记得清空数组。
代码：
#pragma GCC optimize(2)
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef pair<int,int>PII;
inline ll read(){
ll x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if (ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x<<1) + (x<<3) + (ch^48);
ch = getchar();
}
return x * f;
}
const int maxn=1e6+7;
int h[maxn],e[maxn],w[maxn],ne[maxn],idx;
int n,m,r,t;
int d[maxn],cnt[maxn];
bool st[maxn];
void add(int a,int b,int c){
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int spfa(){
memset(d,0x3f, sizeof d);
memset(cnt, 0, sizeof cnt);
memset(st, 0, sizeof st);
queue<int>q;
q.push(1);
st[1]=1;cnt[1]++;d[1]=0;
while(!q.empty()){
int t=q.front();
q.pop();
st[t]=0;
for(int i=h[t];~i;i=ne[i]){
int j=e[i];
if(d[j]>d[t]+w[i]){
d[j]=d[t]+w[i];
cnt[j]=cnt[t]+1;
if(cnt[j]>=n) return 1;
if(!st[j]){
q.push(j);
st[j]=1;
}
}
}
}
return 0;
}
int main(){
int T=read();
while(T--){
n=read();m=read();
memset(h,-1,sizeof h);
idx=0;
while(m--){
int u,v,w;
u=read();v=read();w=read();
if(w>=0) add(u,v,w),add(v,u,w);
else add(u,v,w);
}
int tmp=spfa();
if(tmp) puts("YES");
else puts("NO");
}
return 0;
}
思路：
还是求负环，要注意初始化数组。
统计当前每个点的最短路所包含的边数，如果>=n，则存在负环。
添加有虫洞的边时，权值应当为-w。
京公网安备 11010502036488号