洛谷P3385 【模板】负环
图论
今天get了 一个 DFS-SPFA 判负环的方法
一般的 BFS-SPFA 判负环 一般就是 不停地做，如果某点第 n+1次加入队列中，那么说明这个图存在负环
然而我并不会证明，期望复杂度是 O(kM) k 大约是在 2 左右 但是其实对于一些极限数据，最坏可以把他卡到 O( NM) 额，这就直接炸飞了是不是，而且据说，一些数据比较强的题目，总会想到卡一卡SPFA的，然后我们换一种思路
因为题目中一定存在一种 负环对吧，所以说假如你某段路径权值和为自然数的时候， 你这一段还不如不走对不对，你还不如直接从第一条负边开始走起， 我们把每个点的 dist设为 0 ，dfs下去如果能够松弛的话就一直松弛下去，这时候的松弛还有另一个含义，因为你设的每个的dist是 0 ，所以能够松弛还说明的到 从起点 s 到这个点的 路径和一直是 负的，我们把在这条路径中的点标记一下，如果下次 有松弛过的点 到这个点，那么说明就有负环另外 要注意从每一个点开始的 DFS-SPFA 求的只是求的 以他为起点的 负环是否存在，因为 每次dfs
如果碰到 不能松弛就不 松弛了，那么也许后面还能够松弛，所以说要枚举每一个点作为松弛起点 另外注意这题的坑点 YE'5' 和 N'0' 不包括引号 然后 注意一下初始化 边表 head 以及cnt 都要清空
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 using namespace std ; 10 11 const int maxn = 200011,maxm = 200011,inf = 1e9 ; 12 struct node{13 int to,val,pre ; 14 }e[2*maxm];15 int T,n,m,x,y,val,cnt ; 16 int head[maxn],dist[maxn] ; 17 bool flag ; 18 bool vis[maxn] ; 19 20 inline void addedge(int x,int y,int v) 21 {22 e[++cnt] = (node){ y,v,head[x] } ; 23 head[ x ] = cnt ; 24 }25 26 inline int read() 27 {28 char ch = getchar() ; 29 int x = 0 , f = 1 ; 30 while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ; ch = getchar() ; } 31 while(ch>='0'&&ch<='9') { x = x*10+ch-48 ; ch = getchar() ; } 32 return x*f ; 33 }34 35 inline void SPFA(int u) 36 {37 int v ; 38 vis[ u ] = 1 ; 39 for(int i=head[u];i;i = e[ i ].pre ) 40 {41 v = e[ i ].to ; 42 if( dist[ u ] + e[ i ].val < dist[ v ] ) 43 {44 dist[ v ] = dist[ u ] + e[ i ].val ; 45 if(vis[ v ]||flag) 46 {47 flag = 1 ; 48 break ; 49 }50 SPFA( v ) ; 51 }52 } 53 vis[ u ] = 0 ; 54 }55 56 int main() 57 {58 T = read() ; 59 while(T--) 60 {61 flag = 0 ; 62 cnt = 0 ; 63 n = read() ; m = read() ; 64 for(int i=1;i<=n;i++) dist[ i ] = 0,vis[ i ] = 0,head[ i ] = 0 ; //065 for(int i=1;i<=m;i++) 66 {67 scanf("%d%d%d",&x,&y,&val) ; 68 addedge(x,y,val) ; 69 if(val>=0) addedge(y,x,val) ; 70 }71 for(int i=1;i<=n;i++) 72 {73 SPFA( i ) ; 74 if(flag) break ; 75 } 76 if(flag) 77 printf("YE5\n") ; 78 else 79 printf("N0\n") ; 80 81 }82 return 0 ; 83 }