首页 > 代码库 > [ 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求负环
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。