http://poj.org/problem?id=3259
POJ 3259 Wormholes
大意：给出由n个顶点组成的有向图所有边信息，判断该图中是否存在负回路
分析：
由于不知道图中的负环路会包含哪些顶点，故自定义一源点s,对于每个顶点k,
有一条s到k权值为0的有向边，此时便可初始化s到每个顶点的距离dis[k]为0，
然后用Bellman-Ford计算从源点s到各点的単源最短路，若存在某条边有第n+1次
松弛操作，则存在负环，否则没有负环
重点注意：引出源点s的定义，并创建从s到每个点的单向边的目的是为更好地理解dis[i]的初值问题，
当然，对于初值dis[]不一定要是0，也可以是其他任意数，
但理解的前提是创建从s到每个点的边必须是单向边且只能是单向。
View Code
1 #include<stdio.h>
2 #include<string.h>
3 constint N =2500+200+5;
4 constint MAX_N =500+5;
5 struct Edge
6 {
7 int from;
8 int to;
9 int cost;
10 }edge[N*2];
11 int ednum;
12 int dis[MAX_N];//dis[i]记录从源点s到i的当前距离
13 //判断图中是否存在负权回路，若不存在返回true
14 bool bellman(int n)
15 {
16 int i,j;
17 memset(dis,0,sizeof(dis));//自定义一源点s,从s到每个顶点存在单向边，距离为0
18
19 for(i=0;i<n;i++)//对每条边进行n次松弛操作
20 {
21 bool changed =false;
22 for(j=0;j<ednum;j++)
23 {
24 int temp = dis[edge[j].from]+edge[j].cost;
25 if(temp<dis[edge[j].to])
26 {
27 dis[edge[j].to]=temp;
28 changed =true;
29 }
30 }
31
32 if(changed==false)returntrue;
33 }
34
35 for(j=0;j<ednum;j++)//进行第n+1次松弛操作，判断有无负回路
36 {
37 if(dis[edge[j].from]+edge[j].cost<dis[edge[j].to])
38 returnfalse;
39 }
40 returntrue;
41 }
42
43 int main()
44 {
45 int F;
46 while(scanf("%d",&F)!=EOF)//农场个数
47 {
48 while(F--)
49 {
50 int n,m,w,i;
51 scanf("%d%d%d",&n,&m,&w);//n个点，m条无向边，w条有向负边
52 ednum =0;
53 for(i=0;i<m;i++)
54 {
55 scanf("%d%d%d",&edge[ednum].from,&edge[ednum].to,&edge[ednum].cost);
56 ednum++;
57 edge[ednum].to=edge[ednum-1].from;
58 edge[ednum].from=edge[ednum-1].to;
59 edge[ednum].cost=edge[ednum-1].cost;
60 ednum++;
61 }
62
63 for(i=0;i<w;i++)
64 {
65 scanf("%d%d%d",&edge[ednum].from,&edge[ednum].to,&edge[ednum].cost);
66 edge[ednum].cost =-edge[ednum].cost;
67 ednum++;
68 }
69
70 if(bellman(n)==false)
71 {
72 printf("YES\n");
73 }
74 else
75 printf("NO\n");
76
77 }
78 }
79 return0;
80 }
81
82
2 #include<string.h>
3 constint N =2500+200+5;
4 constint MAX_N =500+5;
5 struct Edge
6 {
7 int from;
8 int to;
9 int cost;
10 }edge[N*2];
11 int ednum;
12 int dis[MAX_N];//dis[i]记录从源点s到i的当前距离
13 //判断图中是否存在负权回路，若不存在返回true
14 bool bellman(int n)
15 {
16 int i,j;
17 memset(dis,0,sizeof(dis));//自定义一源点s,从s到每个顶点存在单向边，距离为0
18
19 for(i=0;i<n;i++)//对每条边进行n次松弛操作
20 {
21 bool changed =false;
22 for(j=0;j<ednum;j++)
23 {
24 int temp = dis[edge[j].from]+edge[j].cost;
25 if(temp<dis[edge[j].to])
26 {
27 dis[edge[j].to]=temp;
28 changed =true;
29 }
30 }
31
32 if(changed==false)returntrue;
33 }
34
35 for(j=0;j<ednum;j++)//进行第n+1次松弛操作，判断有无负回路
36 {
37 if(dis[edge[j].from]+edge[j].cost<dis[edge[j].to])
38 returnfalse;
39 }
40 returntrue;
41 }
42
43 int main()
44 {
45 int F;
46 while(scanf("%d",&F)!=EOF)//农场个数
47 {
48 while(F--)
49 {
50 int n,m,w,i;
51 scanf("%d%d%d",&n,&m,&w);//n个点，m条无向边，w条有向负边
52 ednum =0;
53 for(i=0;i<m;i++)
54 {
55 scanf("%d%d%d",&edge[ednum].from,&edge[ednum].to,&edge[ednum].cost);
56 ednum++;
57 edge[ednum].to=edge[ednum-1].from;
58 edge[ednum].from=edge[ednum-1].to;
59 edge[ednum].cost=edge[ednum-1].cost;
60 ednum++;
61 }
62
63 for(i=0;i<w;i++)
64 {
65 scanf("%d%d%d",&edge[ednum].from,&edge[ednum].to,&edge[ednum].cost);
66 edge[ednum].cost =-edge[ednum].cost;
67 ednum++;
68 }
69
70 if(bellman(n)==false)
71 {
72 printf("YES\n");
73 }
74 else
75 printf("NO\n");
76
77 }
78 }
79 return0;
80 }
81
82