题意就是问倒腾外币能不能升值
不用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=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_T 105 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 ",cas++,ok?"Yes":"No");//注意是Yes 不是YES 109 } 110 return 0; 111 }