Arbitrage POJ - 2240 最短路Bellman判断正环

  1 #include <cstdio>
  2 #include <fstream>
  3 #include <algorithm>
  4 #include <cmath>
  5 #include <deque>
  6 #include <vector>
  7 #include <queue>
  8 #include <string>
  9 #include <cstring>
 10 #include <map>
 11 #include <stack>
 12 #include <set>
 13 #include <sstream>
 14 #include <iostream>
 15 #define mod 998244353
 16 #define eps 1e-6
 17 #define ll long long
 18 #define INF 0x3f3f3f3f
 19 using namespace std;
 20 
 21 //用于存放货币的转换
 22 struct node
 23 {
 24     //x源来的钱的种类，b转换后钱的种类
 25     int x,y;
 26     //s表示汇率
 27     double s;
 28 };
 29 //ve表示有多少个汇率
 30 vector<node> ve;
 31 //mp用于给货币种类编号
 32 map<string,int> mp;
 33 //dis表示起点转换成其他点后的钱数
 34 double dis[35];
 35 //bellman用于判断是否有正环
 36 //n表示有了n个点，v表示起点
 37 bool bellman(int n,int v)
 38 {
 39     //初始钱数为0；
 40     for(int i=1;i<=n;i++)
 41     {
 42         dis[i]=0;
 43     }
 44     //将起点的钱数设为1，为方便计算
 45     dis[v]=1;
 46     //n-1次遍历
 47     for(int i=1;i<n;i++)
 48     {
 49         //对每个汇率进行遍历
 50         for(int j=0;j<ve.size();j++)
 51         {
 52             int a=ve[j].x;
 53             int b=ve[j].y;
 54             //更新b之间的钱数
 55             if(dis[b]<dis[a]*ve[j].s)
 56             {
 57                 dis[b]=dis[a]*ve[j].s;
 58             }
 59         }
 60     }
 61     //在进行一次遍历，判断是否有正环
 62     for(int j=0;j<ve.size();j++)
 63     {
 64         int a=ve[j].x;
 65         int b=ve[j].y;
 66         //如果钱还能增加，则有正环
 67         if(dis[b]<dis[a]*ve[j].s)
 68         {
 69             return true;
 70         }
 71     }
 72     return false;
 73 }
 74 int main()
 75 {
 76     int n,ans=1;
 77     while(scanf("%d",&n)&&n!=0)
 78     {
 79         string str;
 80         for(int i=1;i<=n;i++)
 81         {
 82             cin>>str;
 83             //对钱的种类进行标记
 84             mp[str]=i;
 85         }
 86         int m;
 87         scanf("%d",&m);
 88         string a,b;
 89         node no;
 90         for(int i=0;i<m;i++)
 91         {
 92             cin>>a>>no.s>>b;
 93             no.x=mp[a];
 94             no.y=mp[b];
 95             //记录汇率
 96             ve.push_back(no);
 97         }
 98         printf("Case %d: ",ans++);
 99         //枚举所有的起点
100         for(int i=1;i<=n;i++)
101         {
102             //判断有正环
103             if(bellman(n,i))
104             {
105                 printf("Yes\n");
106                 break;
107             }//如果到最后一个起点后海没有正环，则表示财富无法增加
108             else if(i==n)
109             {
110                 printf("No\n");
111             }
112         }
113         //清除STL容器的内存
114         ve.clear();
115         mp.clear();
116     }
117 }