首页 > 代码库 > poj3259 Wormholes --- spfa判负环
poj3259 Wormholes --- spfa判负环
又写了个bellman模板一直RE求解啊。。。
#include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <map> #define inf 0x3f3f3f3f #define ll __int64 #define mod 1000000007 using namespace std; struct node { int v,w,next; }e[5300]; int head[550],h,d[550],inq[550],outq[550],n,m,w; void init() { memset(head,-1,sizeof head); h=0; } void addedge(int a,int b,int c) { e[h].v=b; e[h].w=c; e[h].next=head[a]; head[a]=h++; } int spfa(int st) { memset(d,0x3f,sizeof d); memset(inq,0,sizeof inq); memset(outq,0,sizeof outq); d[st]=0;inq[st]=1; queue<int> q; q.push(st); while(!q.empty()) { int x=q.front(); q.pop(); inq[x]=0; outq[x]++; if(outq[x]>n) return 0;//存在负环 for(int i=head[x];i!=-1;i=e[i].next) { if(d[e[i].v]>d[x]+e[i].w) { d[e[i].v]=d[x]+e[i].w; if(!inq[e[i].v]) { inq[e[i].v]=1; q.push(e[i].v); } } } } return 1; } int bellman(int st) { int i,j,k; memset(d,0x3f,sizeof d); d[st]=0; for(i=0;i<n-1;i++)//n-1次松弛操作 { for(j=0;j<n;j++)//枚举每条边 { if(d[j]==inf) continue; for(k=head[j];k!=-1;k=e[k].next) { if(e[k].w!=inf&&d[e[k].v]>d[j]+e[k].w) d[e[k].v]=d[j]+e[k].w; } } } for(j=0;j<n;j++) { if(d[j]==inf) continue; for(k=head[j];k!=-1;k=e[k].next) { if(e[k].w!=inf&&d[e[k].v]>d[j]+e[k].w) return 0; } } return 1; } int main() { int T,a,b,c; scanf("%d",&T); while(T--) { init(); scanf("%d%d%d",&n,&m,&w); for(int i=0;i<m;i++) { scanf("%d%d%d",&a,&b,&c); addedge(a,b,c); addedge(b,a,c); } for(int i=0;i<w;i++) { scanf("%d%d%d",&a,&b,&c); addedge(a,b,-c); } int ans=spfa(1); if(!ans) printf("YES\n"); else printf("NO\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。