首页 > 代码库 > 【洛谷P3385】模板-负环
【洛谷P3385】模板-负环
这道题普通的bfs spfa或者ballen ford会T
所以我们使用dfs spfa
原因在于,bfs sfpa中每个节点的入队次数不定,退出操作不及时,而dfs则不会
既然,我们需要找负环,那么我们不妨将dis数组初始化为0,以每个点为起点进行dfs spfa
这样第一次扩展到的只有边权为负的边,之后若再次走到以访问过的点一定是负权回路
记得每次更换起点时清零vis数组
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=200010,M=400010; 6 int n,m,size,sg,vis[N],d[N]; 7 int head[M],to[M],nxt[M],val[M]; 8 void uni(int x,int y,int z){ 9 size++; 10 nxt[size]=head[x]; 11 head[x]=size; 12 to[size]=y; 13 val[size]=z; 14 } 15 void dfs_spfa(int x){ 16 if (sg) return; 17 vis[x]=1; 18 for (int k=head[x];k;k=nxt[k]){ 19 if (sg) return; 20 int y=to[k]; 21 if (d[x]+val[k]<d[y]){ 22 d[y]=d[x]+val[k]; 23 if (vis[y]){ 24 sg=1; 25 return; 26 } 27 else 28 dfs_spfa(y); 29 } 30 } 31 vis[x]=0; 32 } 33 int main(){ 34 int a,b,w,T; 35 scanf("%d",&T); 36 while (T--){ 37 size=sg=0; 38 scanf("%d %d",&n,&m); 39 memset(d,0,sizeof(d)); 40 memset(head,0,sizeof(head)); 41 memset(vis,0,sizeof(vis)); 42 for (int i=1;i<=m;i++){ 43 scanf("%d %d %d",&a,&b,&w); 44 uni(a,b,w); 45 if (w>=0) uni(b,a,w); 46 } 47 for (int i=1;i<=n;i++){ 48 dfs_spfa(i); 49 if (sg) break; 50 } 51 if (sg) printf("YE5\n"); 52 else printf("N0\n"); 53 } 54 return 0; 55 }
【洛谷P3385】模板-负环
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。