图论-环-洛谷P3385【模板】负环

本文主要是介绍图论-环-洛谷P3385【模板】负环，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题有毒啊。。输出的不是“NO”是“N0”，不是“YES”而是“YE5”。被坑了一晚上。
另外，spfa-dfs竟然被卡死了，只能过9个点。换成三行就写完的Bellmam-Ford就AC了

SPFA-DFS代码：

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,r,l) for(int i=(r);i>=(l);i--)
#define random(l,r) ((l)+rand()%((r)-(l)+1))
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=1e9+10,N=210000,M=2e5+100000;
const double eps=1e-6;
int n,m,dis[N],t,minedge;
int head[N],nxt[M],to[M],w[M],len;
bool ex,vis[N];
int sign,v; char c;
inline int read(){sign=v=0;while(!isdigit(c=getchar())) if(c=='-') break;if(c=='-') sign=-1; else v=c-'0';while(isdigit(c=getchar())) v=v*10+c-'0';if(sign==0) return v; else return -v;
}
inline void addedge(int a,int b,int ww){ nxt[++len]=head[a]; head[a]=len; to[len]=b; w[len]=ww; }
void spfa(int v){if(ex) return;vis[v]=true;for(int i=head[v];i!=-1;i=nxt[i]){int u=to[i];if(dis[u]<minedge-70100){ex=true;return;}if(dis[v]+w[i]<dis[u]){dis[u]=dis[v]+w[i];if(!vis[u]) spfa(u); else ex=true;if(ex) return;}}vis[v]=false;
}
bool negative_loop_detect(){ex=false;memset(dis,0,sizeof(dis));memset(vis,false,sizeof(vis));rep(i,1,n){spfa(i);if(ex) return true;}return false;
}
int x,y,z;
int main(){int t=read(); minedge=inf;while(t--){memset(head,-1,sizeof(head)); len=0;n=read(); m=read();rep(i,1,m){x=read(); y=read(); z=read();addedge(x,y,z); minedge=min(minedge,z);if(z>=0) addedge(y,x,z);}if(negative_loop_detect()) puts("YE5");else puts("N0");}return 0;
}

Bellman-Ford代码：

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,r,l) for(int i=(r);i>=(l);i--)
#define random(l,r) ((l)+rand()%((r)-(l)+1))
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=1e9+10,N=210000,M=2e5+100000;
const double eps=1e-6;
int n,m,dis[N],t,minedge;
int head[N],nxt[M],to[M],w[M],len;
bool ex,vis[N];
int sign,v; char c;
inline int read(){sign=v=0;while(!isdigit(c=getchar())) if(c=='-') break;if(c=='-') sign=-1; else v=c-'0';while(isdigit(c=getchar())) v=v*10+c-'0';if(sign==0) return v; else return -v;
}
inline void addedge(int a,int b,int ww){ nxt[++len]=head[a]; head[a]=len; to[len]=b; w[len]=ww; }
bool bellmanford(){memset(dis,0x3f,sizeof(dis)); dis[1]=0;rep(k,1,n-1) rep(v,1,n) for(int i=head[v];i!=-1;i=nxt[i]) dis[to[i]]=min(dis[to[i]],dis[v]+w[i]);rep(v,1,n) for(int i=head[v];i!=-1;i=nxt[i]) if(dis[to[i]]>dis[v]+w[i]) return true;return false;
}
int x,y,z;
int main(){t=read(); minedge=inf;while(t--){memset(head,-1,sizeof(head)); len=0;n=read(); m=read();rep(i,1,m){x=read(); y=read(); z=read();addedge(x,y,z); //minedge=min(minedge,z);if(z>=0) addedge(y,x,z);}if(bellmanford()) puts("YE5");else puts("N0");}return 0;
}

突发奇想，把负环改成正环做，于是可以加入一个新的剪枝——maxedge，也就是判断当前点的dis是否大于maxedge，若大于就说明有正环了。（负环不能加这个剪枝，会WA，不知道是不是我姿势不对）期盼着可以A掉本来T的第9个点，然而该T的还是T了，这个故事告诉我们如果求负环的时候如果数据范围在Bellman-Ford可以解决的范围内就用Bellman-Ford，大于了以后才用SPFA-DFS。

代码如下：

#include<bits/stdc++.h>
#define rep(i,l,r) for(register int i=(l);i<=(r);i++)
#define per(i,r,l) for(register int i=(r);i>=(l);i--)
#define random(l,r) ((l)+rand()%((r)-(l)+1))
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=1e9+10,N=210000,M=2e5+100000;
const double eps=1e-6;
int n,m,dis[N],t,maxedge;
int head[N],nxt[M],to[M],w[M],len;
bool ex,vis[N];
inline int read(){register int sign=0,v=0; register char c;while(!isdigit(c=getchar())) if(c=='-') break;if(c=='-') sign=-1; else v=c-'0';while(isdigit(c=getchar())) v=v*10+c-'0';if(sign==0) return v; else return -v;
}
inline void addedge(int a,int b,int ww){ nxt[++len]=head[a]; head[a]=len; to[len]=b; w[len]=ww; }
void spfa(int v){if(ex) return;vis[v]=true;for(int i=head[v];i!=-1;i=nxt[i]){int u=to[i];if(dis[u]>maxedge){ex=true;return;}if(dis[v]+w[i]>dis[u]){dis[u]=dis[v]+w[i];if(!vis[u]) spfa(u); else ex=true;if(ex) return;}}vis[v]=false;
}
bool positive_loop_detect(){ex=false;memset(dis,128,sizeof(dis));memset(vis,false,sizeof(vis));rep(i,1,n){spfa(i);if(ex) return true;}return false;
}
int x,y,z;
int main(){int t=read();while(t--){memset(head,-1,sizeof(head)); len=0; maxedge=-inf;n=read(); m=read();rep(i,1,m){x=read(); y=read(); z=read(); z=-z;//将负环转化成正环 addedge(x,y,z); maxedge=max(maxedge,z);if(z<=0) addedge(y,x,z);}if(positive_loop_detect()) puts("YE5");else puts("N0");}return 0;
}