Currency Exchange(POJ1860 判正环)

~题目链接~

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[i]=maxn;
26     Q.push(s);
27     dis[s]=k;
28     flag[s]=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[i]<(dis[h]-map[h][i].y)*map[h][i].x)//松弛
36             {
37                 dis[i]=(dis[h]-map[h][i].y)*map[h][i].x;
38                 if(!flag[i])
39                 {
40                     Q.push(i);
41                     flag[i]=1;
42                 }
43             }
44         if(dis[s]>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][b].x=u;
60             map[a][b].y=v;
61             map[b][a].x=w;
62             map[b][a].y=z;
63         }
64         if(Spfa(n,s,k))
65             printf("YES
");
66         else
67             printf("NO
");
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[s]=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
");
52         else
53             printf("NO
");
54     }
55     return 0;
56 }

View Code