poj 1860 Currency Exchange

题意：

有多种汇币，汇币之间可以交换，这需要手续费，当你用100A币交换B币时，A到B的汇率是29.75，手续费是0.39，那么你可以得到(100 - 0.39) * 29.75 = 2963.3975 B币。问s币的金额经过交换最终得到的s币金额数能否增加

分析：

相当于求正权回路，dis[a]表示a点的资金。若dis[b]<(dis[a]-a转化b的手续费)*rate,显然可以更新dis[b]=(dis[a]-a转化b的手续费)*rate。以此类推，如果可以使金额增加，则说明可以存在一个回路不断增加金币数。

一点小想法：

开始有个想法，那就是觉得正权回路必须经过s，在想怎么判断产生的回路经不经过s。后来看了下discuss有人觉得没有判也能过是因为数据弱。其实题目给的rate>0的。

即：假如不包含s点。那么因为初始化时其他dis[]都是0，所以不可能有dis[edge[i].e]<(dis[edge[i].s]-edge[i].c)*edge[i].r成立。左边为0(左边不为0时肯定已经与s点交换过了),右边<0。所以其实这个已经肯定了是回路包含s点。

1     for(int i=0;i<pe;i++)
2             if(dis[edge[i].e]<(dis[edge[i].s]-edge[i].c)*edge[i].r)
3             {
4                 dis[edge[i].e]=(dis[edge[i].s]-edge[i].c)*edge[i].r;
5                 sign=true;
6             }

代码：

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 struct Edge
 9 {
10     int s,e;
11     double r;
12     double c;
13 }edge[210];
14 
15 int pe;
16 int N,M,S;
17 double V;
18 double dis[110];
19 
20 bool bellman_ford()
21 {
22     bool sign;
23 
24     memset(dis,0,sizeof(dis));
25     dis[S]=V;
26     for(int j=0;j<N+1;j++)
27     {
28         sign=false;
29         for(int i=0;i<pe;i++)
30             if(dis[edge[i].e]<(dis[edge[i].s]-edge[i].c)*edge[i].r)
31             {
32                 dis[edge[i].e]=(dis[edge[i].s]-edge[i].c)*edge[i].r;
33                 sign=true;
34             }
35         if(!sign)
36             break;
37     }
38     if(sign)
39         return false;
40     else
41         return true;
42 }
43 
44 int main()
45 {
46     while(scanf("%d%d%d%lf",&N,&M,&S,&V) != EOF)
47     {
48         pe=0;
49 
50         int a,b;
51         double rab,cab,rba,cba;
52 
53         for(int i=0;i<M;i++)
54         {
55             scanf("%d%d%lf%lf%lf%lf",&a,&b,&rab,&cab,&rba,&cba);
56             edge[pe].s=a;
57             edge[pe].e=b;
58             edge[pe].r=rab;
59             edge[pe++].c=cab;
60             edge[pe].s=b;
61             edge[pe].e=a;
62             edge[pe].r=rba;
63             edge[pe++].c=cba;
64         }
65         if(bellman_ford())
66             puts("NO");
67         else
68             puts("YES");
69     }
70     return 0;
71 }