题解 P3385 【【模板】负环】

萌新题解，有点方 自以为还是写的相当简洁的 主要思想是用**dfs实现SPFA**， 简化判负环 具体看注释吧，会bfs型SPFA的一般都看得懂了 好吧，由于数据更新，dfs的挂了，请往下看 ------------ ```cpp #include<bits/stdc++.h> using namespace std; int t,n,m,cnt=0; int dis[210000],vis[210000],head[210000]; bool flg; struct xx { int next,to,w; } e[410000]; inline void add(int u,int v,int w) { e[++cnt].to=v; e[cnt].next=head[u]; e[cnt].w=w; head[u]=cnt; } void spfa(int u) { //dfs型SPFA vis[u]=1; //将该节点标记为访问过 for(int i=head[u]; i; i=e[i].next) { int v=e[i].to; if(dis[v]>dis[u]+e[i].w) {//松弛操作 if(vis[v]||flg) {flg=1;break;}//若回到了已访问过的节点，则一定存在负环 dis[v]=dis[u]+e[i].w; spfa(v); } } vis[u]=0; //该节点并不在负环中，将该点取消标记 } int main() { scanf("%d",&t); while(t--) { memset(e,0,sizeof(e)); cnt=0; memset(dis,0,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(head,0,sizeof(head)); //初始化数组 scanf("%d%d",&n,&m); int a,b,w; for(int i=1; i<=m; i++) { scanf("%d%d%d",&a,&b,&w); add(a,b,w); if(w>=0) add(b,a,w); } flg=0; for(int i=1; i<=n; i++) { spfa(i); //以每个点为起点SPFA一次 if(flg) break; } if(flg) puts("YE5"); else puts("N0"); //天大的坑点 } return 0; } ``` ------------ ### 二更 得知数据被莫名加强，感到大为震惊， 为不~~误人子弟~~，连夜来修题解5555~ 好吧，只能用bfs了，具体来说就是当某个点被松弛次数≥N时必定存在负环 ~~有一个小小的优化是dis数组的初值可赋为0，可大大减少正边的松弛次数~~ 发现这样是不对，当s=1，将会不进行松弛？ 感谢@DefFrancis的指正 ------------ ```cpp #include<ctype.h> #include<cstring> #include<cstdio> using namespace std; int n,m,dis[10010],q[50001000],head[10100],cnt,countc[10100]; int vis[10010]; inline int read(){ int x=0,f=1; char ch; ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();} while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();} return x*f; } struct node { int nxt,tt,dis; } Map[100000]; void addedge(int a,int b,int c) { cnt++; Map[cnt].dis=c; Map[cnt].tt=b; Map[cnt].nxt=head[a]; head[a]=cnt; } inline int SPFA() { int l=0,r=1; memset(dis,0,sizeof(dis)); dis[1]=0; //初始化 ，值赋为0！ memset(vis,0,sizeof(vis)); vis[1]=1; memset(countc,0,sizeof countc); countc[1]=1; q[r]=1; //将起点入队 while(l<r) { int h=q[++l]; vis[h]=0; //队头出队 for(int i=head[h]; i; i=Map[i].nxt) //遍历当前点的所有联通点 if(dis[h]+Map[i].dis<dis[Map[i].tt])//松弛操作 { if(++countc[Map[i].tt]>=n) return 1; //若被松弛>=n次，则存在负环 dis[Map[i].tt]=dis[h]+Map[i].dis; if(!vis[Map[i].tt]) { //若该点不在队列中，将该点入队 q[++r]=Map[i].tt; vis[Map[i].tt]=1; } } } return 0; } int main() { int t; t=read(); while(t--){ cnt=0; memset(head,0,sizeof head); n=read(); m=read(); for(int i=1,a,b,c; i<=m; i++) { a=read(),b=read(),c=read(); addedge(a,b,c); if(c>=0) addedge(b,a,c); } if(SPFA()) puts("YE5"); else puts("N0"); } } ``` 哎，为此贡献了一页的错误记录>_<