poj 1860 Currency Exchange (最短路bellman_ford思想找正权环 最长路)

yanqiufang

　　感觉最短路好神奇呀，刚开始我都 没想到用最短路
　　题目：http://poj.org/problem?id=1860
　　题意：有多种从a到b的汇率，在你汇钱的过程中还需要支付手续费，那么你所得的钱是 money=（nowmoney-手续费）*rate，现在问你有v钱，从s开始出发交换钱能不能赚钱
　　题解：这题其实是用bellman_ford的思想，通过n-1次松弛后，如果还能增加，就说明有环 可以使金钱数不断增加。



1 #include <iostream>
2  #include<cstdio>
3  #include<cstring>
4  #include<cstdlib>
5  #include<stack>
6  #include<queue>
7  #include<cmath>
8  #include<algorithm>
9  using namespace std;
10  int cnt;
11  double dis[1000];
12  double n,m,v;
13  struct node
14  {
15      int u,v,next;
16      double r,c;
17  }edge[1000];
18  
19  void add(int u,int v,double r,double c)
20  {
21      edge[cnt].u=u; edge[cnt].v=v;
22      edge[cnt].r=r; edge[cnt++].c=c;
23  }
24  int bellman_ford(int s)
25  {
26      int i,j;
27      for(i=0; i<n; i++)
28      dis=0;
29      dis=v;  //跟最短路不一样，到自己的距离是原来的钱数
30      for(i=0; i<n-1; i++)
31      for(j=0; j<cnt; j++)
32      {
33          if(dis[edge[j].v]<(dis[edge[j].u]-edge[j].c)*edge[j].r)//逆用最短路
34          dis[edge[j].v]=(dis[edge[j].u]-edge[j].c)*edge[j].r;
35      }
36      for(j=0; j<cnt; j++)
37         if(dis[edge[j].v]<(dis[edge[j].u]-edge[j].c)*edge[j].r)//如果成立说明有能使钱数增加的环
38          return 1;
39      return 0;
40  }
41  int main()
42  {
43      int s,i,j,a,b;
44      double rab,cab,rba,cba;
45      scanf("%lf%lf%d%lf",&n,&m,&s,&v);
46      cnt=0;
47      for(i=0; i<m; i++)
48      {
49          scanf("%d%d%lf%lf%lf%lf",&a,&b,&rab,&cab,&rba,&cba);
50          add(a,b,rab,cab);
51          add(b,a,rba,cba);
52      }
53      if(bellman_ford(s)) printf("YES\n");
54      else printf("NO\n");
55      return 0;
56  }
57  
　　这个博客：http://blog.iyunv.com/wangjian8006/article/details/7871753
　　就是到s的距离大于v了，就是YES。
　　有spfa的代码，这个应该理论上更省时间