Arbitrage POJ

题目链接：https://vjudge.net/problem/POJ-2240
思路：判正环，Bellman-ford和SPFA,floyd都可以，有正环就可以套利。
这里用SPFA，就是个板子题吧，把松弛改成乘法操作就好了。
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <queue>
  6 #include <string>
  7 #include <map>
  8 #include <cmath>
  9 #include <iomanip>
 10 using namespace std;
 11  
 12 typedef long long LL;
 13 #define inf (1LL << 25)
 14 #define rep(i,j,k) for(int i = (j); i <= (k); i++)
 15 #define rep__(i,j,k) for(int i = (j); i < (k); i++)
 16 #define per(i,j,k) for(int i = (j); i >= (k); i--)
 17 #define per__(i,j,k) for(int i = (j); i > (k); i--)
 18 
 19 const int N = 40;
 20 map<string,int > si; //编号，方便建图
 21 int head[N];
 22 bool vis[N];
 23 int tot[N];
 24 double value[N];
 25 int cnt;
 26 int n;
 27 
 28 struct Edge{
 29     int to;
 30     double w;
 31     int next;
 32 }e[1010];
 33 
 34 void add(int u,int v,double w){
 35     e[cnt].to = v;
 36     e[cnt].w = w;
 37     e[cnt].next = head[u];
 38     head[u] = cnt++;
 39 }
 40 
 41 bool SPFA(){
 42 
 43     rep(i,1,n) value[i] = 0;
 44     value[1] = 1000; //随意选个点就行
 45     rep(i,1,n) vis[i] = false;
 46     rep(i,1,n) tot[i] = 0;
 47     vis[1] = true;
 48     queue<int> que;
 49     que.push(1);
 50 
 51     while(!que.empty()){
 52         int u = que.front();
 53         que.pop();
 54         vis[u] = false;
 55 
 56         for(int o = head[u]; ~o; o = e[o].next){
 57             int v = e[o].to;
 58             double w = e[o].w;
 59 
 60             if(value[v] < value[u] * w){
 61                 value[v] = value[u] * w;
 62                 if(!vis[v]){
 63                     vis[v] = true;
 64                     que.push(v);
 65                     tot[v]++;
 66                     if(tot[v] > n - 1) return true; //有正环
 67                 }
 68             }
 69         }
 70     } 
 71 
 72     return false;
 73 
 74 }
 75 
 76 int main(){
 77 
 78     ios::sync_with_stdio(false);
 79     cin.tie(0);
 80 
 81     int tot = 0;
 82     while(cin >> n && n){
 83 
 84         rep(i,1,n) head[i] = -1;
 85         cnt = 0;
 86         si.clear();
 87         string in;
 88         rep(i,1,n){
 89             cin >> in;
 90             si[in] = i;
 91         }
 92 
 93         int m;
 94         string u,v;
 95         double w;
 96         
 97         cin >> m;
 98         rep(i,1,m){
 99             cin >> u >> w >> v;
100             add(si[u],si[v],w);
101         }
102         cout << "Case " << ++tot << ": ";
103         if(SPFA()) cout << "Yes" << endl;
104         else cout << "No" << endl;
105     }
106 
107     
108 
109     getchar(); getchar();
110     return 0;
111 }