POJ-2240 Arbitrage---判断正环+枚举

题目链接：

题目大意：

已知n种货币，以及m种货币汇率及方式，问能否通过货币转换，使得财富增加。

思路：

由于这里问的是财富有没有增加，但是没有源点，所以可以枚举1-n为源点，分别用bellman-ford算法判断是否存在正环，如果有正环那就输出Yes，反之输出No。

这里还需要编号

其实可以用Floyd算法直接出结果判断有没有正环，这里用bellman-ford是卡着时间过的。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<stack>

 #include<map>

 #include<set>

 #include<sstream>

 using namespace std;

 typedef long long ll;

 const int maxn =  + ;

 const int INF =  << ;

 int T, n, m, cases, tot;

 map<string, int>id;

 set<string>cnt;

 struct edge

 {

     int u, v;

     double r;

     edge(int u, int v, double r):u(u), v(v), r(r){}

     edge(){}

 };

 edge a[maxn];

 int getid(string s)

 {

     if(cnt.count(s))return id[s];

     cnt.insert(s);

     return id[s] = cnt.size();

 }

 double d[maxn];

 bool Bellman(int u)

 {

     for(int i = ; i <= n; i++)d[i] = 1.0 * INF;

     d[u] = ;

     for(int i = ; i < n; i++)

     {

         for(int j = ; j < tot; j++)

         {

             int x = a[j].u, y = a[j].v;

             double r = a[j].r;

             if(d[x] * r > d[y])

             {

                 d[y] = d[x] * r;

                 if(i == n - )return true;//第n次迭代还有更新说明存在正环

             }

         }

     }

     return false;

 }

 int main()

 {

     while(cin >> n && n)

     {

         string s;

         cnt.clear();

         id.clear();

         tot = ;

         bool flag = ;

         for(int i = ; i < n; i++)

         {

             cin >> s;

             getid(s);

         }

         cin >> m;

         string s1, s2;

         double r;

         for(int i = ; i < m; i++)

         {

             cin >> s1 >> r >> s2;

             int u = getid(s1);

             int v = getid(s2);

             a[tot++] = edge(u, v, r);

         }

         printf("Case %d: ", ++cases);

         for(int i = ; i <= n; i++)

         {

             if(Bellman(i))

             {

                 flag = ;

                 break;

             }

         }

         if(flag)printf("Yes\n");

         else printf("No\n");

     }

     return ;

 }