Currency Exchange(POJ1860 判正环)

shanghaipc

　　~题目链接~
　　http://poj.org/problem?id=1860
Sample Input

3 2 1 20.0
1 2 1.00 1.00 1.00 1.00
2 3 1.10 1.00 1.10 1.00

Sample Output

YES
　　1.Spfa





1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 #include<queue>
5 #define maxn 2<<28
6 #define maxm 1000+10
7
8 using namespace std;
9
10 struct node
11 {
12     double x,y;
13 } map[maxm][maxm];
14
15 double dis[maxm];
16 queue<int>Q;
17
18 int Spfa(int n,int s,double k)
19 {
20     while(!Q.empty())
21         Q.pop();
22     int flag[maxm],i;
23     memset(flag,0,sizeof(flag));
24     for(i=1; i<=n; i++)
25         dis=maxn;
26     Q.push(s);
27     dis=k;
28     flag=1;
29     while(!Q.empty())
30     {
31         int h=Q.front();
32         Q.pop();
33         flag[h]=0;
34         for(i=1; i<=n; i++)
35             if(dis<(dis[h]-map[h].y)*map[h].x)//松弛
36             {
37                 dis=(dis[h]-map[h].y)*map[h].x;
38                 if(!flag)
39                 {
40                     Q.push(i);
41                     flag=1;
42                 }
43             }
44         if(dis>k)//判断是否存在正环
45             return 1;
46     }
47     return 0;
48 }
49
50 int main()
51 {
52     int n,m,s,a,b,i;
53     double k,u,v,w,z;
54     while(~scanf("%d%d%d%lf",&n,&m,&s,&k))
55     {
56         for(i=0; i<m; i++)
57         {
58             scanf("%d%d%lf%lf%lf%lf",&a,&b,&u,&v,&w,&z);
59             map[a].x=u;
60             map[a].y=v;
61             map[a].x=w;
62             map[a].y=z;
63         }
64         if(Spfa(n,s,k))
65             printf("YES\n");
66         else
67             printf("NO\n");
68     }
69     return 0;
70 }
View Code 　　2.Bellman_ford





1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 #define maxm 1000+10
5
6 struct node
7 {
8     int u,v;
9     double x,y;
10 } map[maxm];
11
12 double dis[maxm];
13 int num;
14
15 int Bellman_ford(int n,int s,double k)
16 {
17     int i,j,flag;
18     memset(dis,0,sizeof(dis));
19     dis=k;
20     for(i=0; i<n; i++)
21     {
22         flag=0;
23         for(j=1; j<=num; j++)
24             if(dis[map[j].v]<(dis[map[j].u]-map[j].y)*map[j].x)
25             {
26                 dis[map[j].v]=(dis[map[j].u]-map[j].y)*map[j].x;
27                 flag=1;
28             }
29         if(!flag)
30             break;
31     }
32     if(i>=n)//判断松弛后，是否存在正环
33         return 1;
34     return 0;
35 }
36
37 int main()
38 {
39     int n,m,s,a,b,i;
40     double k,u,v,w,z;
41     while(~scanf("%d%d%d%lf",&n,&m,&s,&k))
42     {
43         num=0;
44         for(i=0; i<m; i++)
45         {
46             scanf("%d%d%lf%lf%lf%lf",&a,&b,&u,&v,&w,&z);
47             map[++num]=((struct node){a,b,u,v});
48             map[++num]=((struct node){b,a,w,z});
49         }
50         if(Bellman_ford(n,s,k))
51             printf("YES\n");
52         else
53             printf("NO\n");
54     }
55     return 0;
56 }
View Code