poj

tigh

　　最短路问题，用Bellman算法判断有无正向环。



1 #include <stdio.h>
2 double M[105],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[205];
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[i<<1].init(a,b,q,w);
22         ed[i<<1|1].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[v])
39             {M[v] = (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[v])
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 }