poj
最短路问题，用Bellman算法判断有无正向环。1 #include <stdio.h>
2 double M,orig;
3 int m,n,s;
4 typedef struct
5 {
6 int u,v;
7 double r,c;
8 void init(int a,int b,double q,double p)
9 {u = a; v = b; r = q; c = p;}
10 }Edge;
11 Edge ed;
12 void read_graph()
13 {
14 int a,b,i;
15 double q,w,e,r;
16 for(i = 1; i <= n; i++)
17 M = 0.0;
18 for(i = 0; i < m; i++)
19 {
20 scanf("%d%d%lf%lf%lf%lf",&a,&b,&q,&w,&e,&r);
21 ed.init(a,b,q,w);
22 ed.init(b,a,e,r);
23 }
24 }
25 bool Bellman()
26 {
27 int i,j,u,v;
28 double r,c;
29 bool ok;
30 M = orig;
31 for(j = 1; j < n; j++)
32 {
33 ok = 1;
34 for(i = 0; i < 2*m; i++)
35 {
36 u = ed.u; v = ed.v;
37 r = ed.r; c = ed.c;
38 if((M-c)*r > M)
39 {M = (M-c)*r; ok = 0;}
40 }
41 if(ok) break;
42 }
43 for(i = 0; i < 2*m; i++)
44 {
45 u = ed.u; v = ed.v;
46 r = ed.r; c = ed.c;
47 if((M-c)*r > M)
48 return 1;
49 }
50 return 0;
51 }
52 int main()
53 {
54 while(~scanf("%d%d%d%lf",&n,&m,&s,&orig))
55 {
56 read_graph();
57 if(Bellman())
58 printf("YES\n");
59 else printf("NO\n");
60 }
61 return 0;
62 }
页:
[1]