E - Currency Exchange————Bellman-Ford算法的变形

Myth丶恋晨 2023-06-10 10:29 31阅读 0赞

https://vjudge.net/contest/313997\#problem/E

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<vector>
    using namespace std;
    struct node
    { 
        int u;
        int v;
        double R;
        double C;
    
    };
    vector<node>E;
    int n, m, s;
    double V;
    bool ford()
    { 
        double dis[122];
        for(int i = 0;i <= n;i++)
        { 
            dis[i] = 0;
        }
        dis[s] = V;
    
        for(int i = 0; i < n-1; i++)
        { 
            for(int i = 0; i < E.size(); i++)
            { 
                int u, v;
                double r, c;
                u = E[i].u;
                v = E[i].v;
                r = E[i].R;
                c = E[i].C;
                if((dis[u]-c)*r > dis[v])
                { 
                    dis[v] = (dis[u]-c)*r;
                }
            }
        }
    
        for(int i = 0; i < E.size(); i++)// 查看是否存在一个环路使他能增大 
        { 
            int u, v;
            double r, c;
            u = E[i].u;
            v = E[i].v;
            r = E[i].R;
            c = E[i].C;
            if((dis[u]-c)*r > dis[v])
            { 
                return true;
            }
        }
    
        return false;
    }
    int main()
    { 
        ios_base::sync_with_stdio(false);
    
    
    
        cin>>n>>m>>s>>V;
        E.clear();
        for(int i = 0; i < m; i++)
        { 
            int  f, t;
            double r1, c1, r2, c2;
            cin>>f>>t>>r1>>c1>>r2>>c2;
    
            node tmp;
            tmp.u = f;
            tmp.v = t;
            tmp.R = r1;
            tmp.C = c1;
            E.push_back(tmp);
            tmp.v = f;
            tmp.u = t;
            tmp.R = r2;
            tmp.C = c2;
            E.push_back(tmp);
        }
        bool ans = ford();
    
        if(ans)
        { 
            printf("YES");
        }
        else printf("NO");
    
    
        return 0;
    }