I - Arbitrage POJ - 2240 ————floyd +负环+逆向思维

超、凢脫俗 2023-05-30 14:55 29阅读 0赞

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

/***** 将边转换为 反向边， 如果反向边 存在 负环（能减小的环路） 就表示 原图存在 能增加的环 *******/
    
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<map>
    #include<string>
    using namespace std;
    const int maxn = 35;
    const double inf = 1e9;
    double mp[maxn][maxn];
    map<string, int>name;
    int n;
    int m;
    
    void init()
    { 
         name.clear();
         for(int i = 0;i < n;i++)
         { 
             for(int j = 0;j < n;j++)
             { 
                i == j ? mp[i][j] = 1:mp[i][j] = inf;
             }
    
         }
    
    }
    bool floyd()
    { 
    
        for(int k = 0;k < n;k++)
        { 
            for(int i = 0;i < n;i++)
            { 
                for(int j = 0;j < n;j++)
                { 
                    if(mp[i][k]!= inf&&mp[k][j]!= inf&&mp[i][j] > mp[i][k]* mp[k][j])
                    { 
                        mp[i][j]  = mp[i][k]*mp[k][j];
                    }
                }
                if(mp[i][i] < 1)
                { 
                    return true;
                }
            }
        }
    
        return false;
    }
    int main()
    { 
        ios_base::sync_with_stdio(false);
        int cnt = 0;
        while(cin>>n&& n != 0)
        { 
           cnt++;
            init();
            for(int i = 0;i < n;i++)
            { 
                char tmp[30];
                cin>>tmp;
                name[tmp] = i;
            }
            cin>>m;
            for(int i = 0;i < m;i++)
            { 
                char a[30];
                double trans;
                char b[30];
    
                cin>>a>>trans>>b;
    
                int u, v;
                u = name[a];
                v = name[b];
                if(1/trans < mp[u][v])
                { 
                    mp[u][v] = 1/trans;
                }
            }
            bool ans = floyd();
            cout<<"Case "<<cnt<<": ";
            if(ans)
            { 
                cout<<"Yes"<<endl;
            }
            else cout<<"No"<<endl;
        }
    
        return 0;
    }