poj1860(Currency Exchange)

赤锋

　　题目大意:
　　给你几个国家的货币兑换率，看你是否能通过不同国家的货币兑换之后是自己的财富增加，如增加输出YES，无法增加输出NO。
　　具体兑换过程：
　　N代表几个国家，M代表几条兑换的信息，S代表起始的国家，V代表你现有的财富金额。
　　从A兑换到B 得到的财富 ：（V-Cab）*Rab 、
　　测试数据：1 2 1.00 1.00 1.00 1.00 1.00 。代表1-2兑换的Rab、Cab是1.00 1.00.  2-1的兑换的Rab和Cab是后两位浮点数1.00 1.00。
　　
　　解题思路：
　　通过Bellman_ford 看是否有正权回路，如果有正权回路，说明财富持续增加输出YES，否则输出NO。
　　
　　代码：





  1 #include <algorithm>
  2 #include <iostream>
  3 #include <sstream>
  4 #include <cstdlib>
  5 #include <cstring>
  6 #include <cstdio>
  7 #include <string>
  8 #include <bitset>
  9 #include <vector>
10 #include <queue>
11 #include <stack>
12 #include <cmath>
13 #include <list>
14 #include <map>
15 #include <set>
16 using namespace std;
17 /***************************************/
18 #define ll long long
19 #define int64 __int64
20 /***************************************/
21 const int INF = 0x7f7f7f7f;
22 const double eps = 1e-8;
23 const double PIE=acos(-1.0);
24 const int d1x[]= {0,-1,0,1};
25 const int d1y[]= {-1,0,1,0};
26 const int d2x[]= {0,-1,0,1};
27 const int d2y[]= {1,0,-1,0};
28 const int fx[]= {-1,-1,-1,0,0,1,1,1};
29 const int fy[]= {-1,0,1,-1,1,-1,0,1};
30 /***************************************/
31 void openfile()
32 {
33     freopen("data.in","rb",stdin);
34     freopen("data.out","wb",stdout);
35 }
36 /**********************华丽丽的分割线,以上为模板部分*****************/
37 #define MAX 0
38 #define N 9010
39 int nodenum, edgenum, w; //点，边，起点
40 typedef struct Edge //边
41 {
42     int u, v;
43     double c,r;
44 } Edge;
45 Edge edge[N];
46 double dis[N];
47 int d;
48 bool Bellman_Ford(int s,double w)
49 {
50     for(int i = 1; i <= nodenum; ++i) //初始化
51         dis=MAX;
52     dis=w;
53     for(int i = 1; i <= nodenum-1; ++i)
54         for(int j=1; j<=d-1; ++j)
55             if(dis[edge[j].u]>0&&dis[edge[j].v]<(dis[edge[j].u]-edge[j].c)*edge[j].r) //松弛（顺序一定不能反~）
56                 dis[edge[j].v] =(dis[edge[j].u]-edge[j].c)*edge[j].r;
57     bool flag = 0;//判断是否含有正权回路
58     for(int j = 1; j <=d-1; ++j)
59        if(dis[edge[j].u]>0&&dis[edge[j].v]<(dis[edge[j].u]-edge[j].c)*edge[j].r)
60         {
61             flag = 1;
62             break;
63         }
64     return flag;
65 }
66 /*
67 上边是正常的判断回路，通过至少边数N-1的循环之后，再判断下各点是否能够更新dis数组，如果更新说明出现回路。
68 然而这题可以通过下面的方法做，原因是给你N条边但是实际记录的2*N条边，所以第一个for循环循环到2*N-1可以得出正确结果，
69 因为超过了N-1次循环，所以足可以判断是否有正权回路，下面的bellman_ford函数的flag是判断如果后面的循环中有任意一次没
70 进入if说明不存在正权回路，因为如果是正权回路，每一次必然会进入if。
71 bool Bellman_Ford(int s,double w)
72 {
73     for(int i = 1; i <= nodenum; ++i) //初始化
74         dis=MAX;
75     dis=w;
76     bool flag;
77     for(int i = 1; i <= nodenum-1; ++i)
78     {
79         flag=true;
80         for(int j=1; j<=d-1; ++j)
81             if(dis[edge[j].u]>0&&dis[edge[j].v]<(dis[edge[j].u]-edge[j].c)*edge[j].r) //松弛（顺序一定不能反~）
82             {
83                 flag=false;
84                 dis[edge[j].v] =(dis[edge[j].u]-edge[j].c)*edge[j].r;
85             }
86         if (flag)
87             return false;
88     }
89     return true;
90 }
91 */
92 int main()
93 {
94     int u,v;
95     double c,r;
96     int s;
97     double w;
98     while(scanf("%d%d%d%lf", &nodenum, &edgenum,&s,&w)!=EOF)
99     {
100         d=1;
101         for(int i = 1; i <= edgenum; ++i)
102         {
103             scanf("%d%d%lf%lf",&u,&v,&r,&c);
104             edge[d].u=u;
105             edge[d].v=v;
106             edge[d].c=c;
107             edge[d].r=r;
108             d++;
109             scanf("%lf%lf",&r,&c);
110             edge[d].u=v;
111             edge[d].v=u;
112             edge[d].c=c;
113             edge[d].r=r;
114             d++;
115         }
116         if(Bellman_Ford(s,w))
117             printf("YES\n");
118         else
119             printf("NO\n");
120     }
121     return 0;
122 }
View Code