本文共 1129 字，大约阅读时间需要 3 分钟。
根据连续的和建图，然后判断是否有负环。注意细节，加上超级源点后，有n+1个点。忘了初始化了，让我WA了N次啊。
#include #include #include #include #include #include #include #include using namespace std;#define N 1001struct node{ int u,v,w,next;}edge[N];int first[N],d[N];int t;void add(int u,int v,int w){ edge[t].u = u; edge[t].v = v; edge[t].w = w; edge[t].next = first[u]; first[u] = t; t ++;}void CL(){ t = 1; memset(first,-1,sizeof(first));}int main(){ int n,m,x,y,w,i,flag,j; int u,v; char ch[10]; while(scanf("%d",&n)!=EOF) { if(n == 0) break; scanf("%d",&m); CL(); for(i = 1;i <= m;i ++) { scanf("%d%d%s%d",&x,&y,ch,&w); if(ch[0] == 'g') { add(x-1,x+y,w+1); } else { add(x+y,x-1,1-w); } } memset(d,0,sizeof(d)); for(i = 1;i <= n+1;i ++) { flag = 1; for(j = 1;j < t;j ++) { u = edge[j].u; v = edge[j].v; if(d[v] < d[u] + edge[j].w) { d[v] = d[u] + edge[j].w; flag = 0; } } if(flag) break; } if(flag == 0) printf("successful conspiracy\n"); else printf("lamentable kingdom\n"); } return 0;}
转载于:https://www.cnblogs.com/naix-x/archive/2013/02/22/2922212.html