POJ - 1860 Currency Exchange

Posted on | In , ,

思路

因为要最后钱变多，那么要么存在一个包含s的环，绕一圈后钱变多，要么是通过不断绕正环增加自己的钱。所以本题我们需要找正环。类比Bellman-ford找负环计算即可，不同在于初始dist数组为0。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define ll long long
#define INF 0x7fffffff
#define ms(a,val) memset((a),(val),(sizeof(a)))

using namespace std;

int n,m,s;
double V;
double dist[1005];
struct edge{
    int u,v;
    double r,c;
    edge(){};
    edge(int u,int v,double r,double c):u(u),v(v),r(r),c(c){};
}e[205];
int bellman_ford(int s,double val){
    ms(dist,0);
    dist[s]=val;
    for(int i=0;i<n;i++){
        for(int j=0;j<2*m;j++){

            if(dist[e[j].v]<(dist[e[j].u]-e[j].c)*e[j].r){
                dist[e[j].v]=(dist[e[j].u]-e[j].c)*e[j].r;
                if(i==n-1)return 1;
            }
        }
    }
    return 0;
}

int main(){
    int u,v;
    double r1,c1,r2,c2;
    while(~scanf("%d%d%d%lf",&n,&m,&s,&V)){
        for(int i=0;i<m;i++){
            scanf("%d%d%lf%lf%lf%lf",&u,&v,&r1,&c1,&r2,&c2);
            e[2*i]=edge(u,v,r1,c1),e[2*i+1]=edge(v,u,r2,c2);
        }
        if(bellman_ford(s,V))printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}