題意是有n個(gè)農(nóng)場(chǎng)，農(nóng)場(chǎng)有N塊地，其中M條路是雙向的，S條路是單向的。雙向的路權(quán)值為正，單向的路權(quán)值為負(fù)。需要判斷有沒(méi)有負(fù)環(huán)。
以下是bellman_ford算法，需要注意的地方在注釋里邊。
1 #include<stdio.h>
2 #include<string.h>
3 #define INF 0x1f1f1f1f
4 #define MAX 5500
5 int dist[MAX/10];
6 struct edge
7 {
8 int u,v,w; //u為起點(diǎn) v為終點(diǎn) w是權(quán)值
9 }edge[MAX];
10 int bellman_ford2(int n,int m,int s) //n個(gè)點(diǎn)，m條邊，起點(diǎn)是s
11 {
12 memset(dist,0x1f1f,sizeof(dist));
13 dist[s]=0;
14 int i,j,k,p,u,v;
15 bool flag;
16 for(i=1;i<n;i++) //n-1次迭代
17 {
18 flag=false; //用來(lái)標(biāo)記某一次是否是更新
19 for(j=0;j<m;j++) //對(duì)每條邊進(jìn)行松弛，即迭代一次
20 {
21 u=edge[j].u;
22 v=edge[j].v;
23 if(dist[v]>dist[u]+edge[j].w)
24 {
25 dist[v]=dist[u]+edge[j].w;
26 flag=true; //如果這一次有某條邊可以松弛
27 }
28 }
29 if(!flag) //如果某一次所有邊都沒(méi)有松弛，
30 return 1; // 可以確定沒(méi)有負(fù)環(huán)，返回 1
31 }
32 flag=false;
33 for(i=0;i<m;i++) //對(duì)所有邊進(jìn)行第n次松弛
34 {
35 u=edge[i].u;
36 v=edge[i].v;
37 if(dist[v]>dist[u]+edge[i].w)
38 {
39 dist[v]=dist[u]+edge[i].w;
40 flag=true;
41 }
42 if(flag) return -1; //如果還有更新，有負(fù)環(huán) 返回 -1
43 }
44 return 1; //否則返回 1
45 }
46 int main()
47 {
48 int i,j,k,m,n,p,q,N,M;
49 int S;
50 scanf("%d",&n);
51 for(i=1;i<=n;i++)
52 {
53 scanf("%d%d%d",&N,&M,&S);
54 int t=0;
55 for(j=1;j<=M;j++)
56 {
57 scanf("%d%d%d",&p,&q,&k);
58 edge[t].u=p; //由于邊是雙向的，需要是兩條
59 edge[t].v=q;
60 edge[t].w=k; t++;
61 edge[t].u=q;
62 edge[t].v=p;
63 edge[t].w=k; t++;
64 }
65 for(j=1;j<=S;j++)
66 {
67 scanf("%d%d%d",&p,&q,&k);
68 edge[t].u=p;
69 edge[t].v=q;
70 edge[t].w=-1*k; t++; //單向的邊權(quán)值為負(fù)
71 }
72 if(bellman_ford2(N,S+2*M,1)==-1) //如果有負(fù)環(huán) YES
73 printf("YES\n");
74 else
75 printf("NO\n");
76 }
77 }
78