【SPFA】POJ1860-Currency Exchange

曾经的美好

　　【题目大意】
　　给出每两种货币之间交换的手续费和汇率，求出从当前货币s开始交换，能否赚。
　　【思路】
　　反向运用SPFA，判断是否有正环。每次队首元素出队之后，判断一下到源点s的距离是否增大，增大则返回true。一开始判断正环的思路如果有一个元素入队超过n次，则说明存在正环。后来发现这个思路是不适用的，因为这个正环中并不一定包含源点..要注意的是：题目中的m并不是边数，边数应该是m*2！所以开数组的时候要尤其注意数组不能开小了。由于C++的判定中如果没有崩掉，不会返回RE只会返回WA，我纠结了好久才找出错因。



1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<queue>
5 using namespace std;
6 struct Rec
7 {
8     int ori,des;
9     double len,val;
10 };
11 const int MAXN=100+5;
12 int first[MAXN],next[MAXN*2];
13 /*用于存储邻接表*/
14 double dis[MAXN];
15 /*存储从s出发到达当前货币的最大值*/
16 int vis[MAXN];
17 /*判断某一个点是否已经存在于队列中*/
18 Rec edge[MAXN*2];
19 int n,m,s;
20 double v;
21
22 bool SPFA()
23 {
24     memset(dis,0,sizeof(dis));
25     memset(vis,0,sizeof(vis));
26     queue<int> que;
27     
28     dis=v;
29     /*默认到持有货币的距离为持有货币的价值*/
30     vis=1;
31     que.push(s);
32     
33     while (!que.empty())
34     {
35         int pos=que.front();
36         int k=first[pos];
37         vis[pos]=0;
38         que.pop();
39         while (k!=-1)
40         {
41             if (dis[edge[k].des]<(dis[pos]-edge[k].len)*edge[k].val)
42             {
43                 dis[edge[k].des]=(dis[pos]-edge[k].len)*edge[k].val;
44                 if (!vis[edge[k].des])
45                 {
46                     vis[edge[k].des]=1;
47                     que.push(edge[k].des);
48                 }
49             }
50             k=next[k];
51         }
52         //if (dis>v) return true;
53     }
54     return false;
55 }
56
57 int main()
58 {
59     scanf("%d%d%d%lf",&n,&m,&s,&v);
60     s--;
61     memset(first,-1,sizeof(first));
62     
63     for (int i=0;i<m;i++)
64     {
65         int a,b;
66         double c1,r1,c2,r2;
67         scanf("%d%d%lf%lf%lf%lf",&a,&b,&r1,&c1,&r2,&c2);
68         a--;
69         b--;
70         edge[i*2].ori=edge[i*2+1].des=a;
71         edge[i*2].des=edge[i*2+1].ori=b;
72         edge[i*2].val=r1;
73         edge[i*2].len=c1;
74         edge[i*2+1].val=r2;
75         edge[i*2+1].len=c2;
76         
77         next[i*2]=first[a];
78         first[a]=i*2;
79         next[i*2+1]=first;
80         first=i*2+1;
81     }
82     m=m*2+2;
83     if (SPFA()) cout<<"YES"<<endl;
84                 else cout<<"NO"<<endl;
85     //system("pause");
86     return 0;
87 }