POJ 1860 Currency Exchange (判正环)

向右看齐 2022-05-17 05:48 166阅读 0赞

[题目链接][Link 1]

题目大意：我们的城市有几个货币兑换点，我们假设每个货币兑换点都只能兑换两种特定的货币，可以有几个货币兑换点，专门兑换同一种货币，每个点都有自己的汇率，A到B的汇率就是1A能够换到的B的价值，同时每个兑换点都有一定的手续费。

例如，如果你想在汇率为29.75的兑换点兑换100美元的卢布，而手续费是0.39，你就会得到(100 - 0.39)\* 29.75 = 2963.3975卢布。

你肯定知道在我们的城市里有N种不同的货币可以进行交易。将这些货币从1-N进行编号。尼克有一些S型号货币，他想知道，在进行一些交易之后，他是否够能增加他的资本。当然，他最终还是想把钱换成S货币。尼克每次操作一定是用的非负的钱。

Input：第一行四个数，N（货币的种类数），M（兑换点的数目），S（尼克手上的钱的类型），V（尼克手上S货币的价值），1<=S<=N<=100, 1<=M<=100，0<=V<=1000。

接下来的M行，每一行有6个数字，整数A和B代表两种货币，然后是从A换到B的汇率以及手续费，从B换到A的汇率以及手续费。

如果能增加S货币的价值就输出“YES”，否则输出“NO”。

分析：一个“兑换点”其实就是图上的两种货币之间有一个兑换环，A到B的权值为(V-Cab)\*Rab，B到A的权值为(V-Cba)\*Rba，最短路中负环会导致路径不断缩小，而此题是需要S货币价值不断增大，所以如果我们能找到存在一个正环，那么S的价值就能不断增大，那么就用bellman-ford来做，不同的是，bellman-ford是判负环，所以在进行初始化的时候，对于不可到达的点的初值不再赋为无限大，而是赋为0，对于源点就直接赋值为V，然后用bellman-ford判一下是否有正环，如果有就输出“YES”，否则输出“NO”。

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<cctype>
    #include<cstring>
    #include<utility>
    #include<cstdlib>
    #include<iomanip>
    #include<iostream>
    #include<algorithm>
    #define inf 0x3f3f3f3f
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    using namespace std;
    const double pi=acos(-1.0);
    const int maxn = 2e2+7;
    const int maxn1 = 1e2+7;
    const double eps = 1e-8;
     
    int n,m,s,tot;
    double dis[maxn1];
    double v;
     
    struct Node{
        int u,v;
        double r,c;//汇率、手续费
    }edge[maxn];
     
    void addEdge(int a,int b,double r,double c)
    {
        edge[tot].u=a;
        edge[tot].v=b;
        edge[tot].r=r;
        edge[tot++].c=c;
    }
     
    bool bellman_ford()
    {
        Clear(dis);/**此处是找正环,与bellman_ford原本赋初值的方式有所不同*/
        dis[s]=v;
        bool flag;
        rfup(i,1,n-1)
        {
            flag=true;
            fup(j,0,tot)
            {
                if(dis[edge[j].v]<(dis[edge[j].u]-edge[j].c)*edge[j].r)
                {
                    flag=false;
                    dis[edge[j].v]=(dis[edge[j].u]-edge[j].c)*edge[j].r;
                }
            }
            if(flag) break;
        }
        fup(i,0,tot)
        {
            if(dis[edge[i].v]<(dis[edge[i].u]-edge[i].c)*edge[i].r)
                return true;
        }
        return false;
    }
     
    int main()
    {
        int a,b;
        double r1,c1,r2,c2;
        while(scanf("%d%d%d%lf",&n,&m,&s,&v)==4)
        {
            tot=0;
            rfup(i,1,m)
            {
                scanf("%d%d%lf%lf%lf%lf",&a,&b,&r1,&c1,&r2,&c2);
                addEdge(a,b,r1,c1);
                addEdge(b,a,r2,c2);
            }
            if(bellman_ford()) printf("YES\n");
            else printf("NO\n");
        }
        return 0;
    }

[Link 1]: http://poj.org/problem?id=1860