首页 > 代码库 > [ An Ac a Day ^_^ ][kuangbin带你飞]专题四 最短路练习 POJ 2240 Arbitrage spfa求负环

[ An Ac a Day ^_^ ][kuangbin带你飞]专题四 最短路练习 POJ 2240 Arbitrage spfa求负环

题意就是问倒腾外币能不能升值

不用spfa 用其他的最短路算法也可以

松弛条件换成dist[v]<dist[u]*e[u][i].value

当然 貌似只有spfa有这个坑……

有A  (value>1.0) A 这种情况……我的天

用Dij Floyd都只用判断如果松弛到了自己 那么一定有环 直接跳出就行

 

  1 #include<cstdio>  2 #include<iostream>  3 #include<algorithm>  4 #include<cmath>  5 #include<cstring>  6 #include<string>  7 #include<ctime>  8 #include<map>  9 #include<set> 10 #include<vector> 11 #include<queue> 12 #include<cstdlib> 13 #include<cassert> 14 #include<sstream> 15 #include<stack> 16 #include<list> 17 #include<bitset> 18 #define cl(a,b) memset(a,b,sizeof(a)) 19 #define debug(x) cerr<<#x<<"=="<<(x)<<endl 20 using namespace std; 21 typedef long long ll; 22  23 const int maxn=1e2+10; 24  25 struct edge 26 { 27     int v; 28     double value; 29     edge(int _v=0,double _value=http://www.mamicode.com/0):v(_v),value(_value) {} 30 }; 31  32 map<string,int>mp; 33 vector<edge>e[maxn]; 34 int n,m; 35 bool vis[maxn],ok; 36 int cnt[maxn]; 37 double dist[maxn]; 38  39 void addedge(int u,int v,double w) 40 { 41     e[u].push_back(edge(v,w)); 42 } 43  44 void init() 45 { 46     ok=false; 47     mp.clear(); 48     for(int i=0;i<maxn;i++) e[i].clear(); 49 } 50  51 bool spfa(int start) 52 { 53     cl(vis,false),cl(dist,0),cl(cnt,0); 54     //注意dist[start]初始化是1 55     vis[start]=true,dist[start]=1.0,cnt[start]=1; 56     queue<int>q; 57     while(!q.empty()) q.pop(); 58     q.push(start); 59     while(!q.empty()) 60     { 61         int u=q.front(); 62         q.pop(); 63         vis[u]=false; 64         for(int i=0; i<e[u].size(); i++) 65         { 66             int v=e[u][i].v; 67             if(dist[v]<dist[u]*e[u][i].value) 68             { 69                 dist[v]=dist[u]*e[u][i].value; 70                 if(!vis[v]) 71                 { 72                     vis[v]=true; 73                     q.push(v); 74                     cnt[v]++; 75                     if(cnt[v]==n) return true; 76                 } 77                 else if(dist[start]>1.0) return true;//特判一下 78             } 79         } 80     } 81     return false; 82 } 83  84 int main() 85 { 86 //    freopen("in.txt","r",stdin); 87     int cas=1; 88     while(~scanf("%d",&n)&&n) 89     { 90         init(); //记得初始化 91         for(int i=0; i<n; i++) 92         { 93             string place; 94             cin>>place; 95             mp[place]=i; 96         } 97         scanf("%d",&m); 98         for(int i=0; i<m; i++) 99         {100             string place1,place2;101             double value;102             cin>>place1>>value>>place2;103             addedge(mp[place1],mp[place2],value);104             //无限WA之后加了下面这句就AC了 T_T105             if(mp[place1]==mp[place2]&&value>1.0) ok=true;106         }107         for(int i=0;i<n&&!ok;i++) ok=spfa(i);108         printf("Case %d: %s\n",cas++,ok?"Yes":"No");//注意是Yes 不是YES109     }110     return 0;111 }

 

[ An Ac a Day ^_^ ][kuangbin带你飞]专题四 最短路练习 POJ 2240 Arbitrage spfa求负环