poj 1860 Currency Exchange (最短路bellman_ford思想找正权环 最长路)
感觉最短路好神奇呀，刚开始我都 没想到用最短路题目：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>
9using namespace std;
10int cnt;
11double dis;
12double n,m,v;
13struct node
14{
15 int u,v,next;
16 double r,c;
17}edge;
18
19void add(int u,int v,double r,double c)
20{
21 edge.u=u; edge.v=v;
22 edge.r=r; edge.c=c;
23}
24int 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.v]<(dis.u]-edge.c)*edge.r)//逆用最短路
34 dis.v]=(dis.u]-edge.c)*edge.r;
35 }
36 for(j=0; j<cnt; j++)
37 if(dis.v]<(dis.u]-edge.c)*edge.r)//如果成立说明有能使钱数增加的环
38 return 1;
39 return 0;
40}
41int 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的代码，这个应该理论上更省时间
页:
[1]