题意：
给了n种硬币的名称，给了m种硬币间的转换关系。
从任意兑换地点开始兑换，看是否能够通过兑换的方式增加金钱。
思路：
用SPFA不断对各个点进行松弛操作，寻找正权值的环。如果找到则输出Yes。
这题测试的时候竟然发现dis数组写成int型...
#include<stdio.h> #include<map> #include<string.h> #include<string> #include<iostream> #include<queue> using namespace std; int n,m; int ednum; bool ok; bool vis[35]; int cnt[35]; double dis[35]; map<string,int>mymap; struct edge { int id; double plu; edge *next; }; edge edges[1005]; edge *adj[35]; inline void addEdge(int a,int b,double c) { edge *tmp; tmp=&edges[ednum]; ednum++; tmp->id=b; tmp->plu=c; tmp->next=adj[a]; adj[a]=tmp; } bool SPFA(int pos) { int id; memset(cnt,0,sizeof(cnt)); for(int i=1;i<=n;i++) { dis[i]=-1; } memset(vis,0,sizeof(vis)); dis[pos]=1; queue<int>q; q.push(pos); vis[pos]=1; cnt[pos]++; while(!q.empty()) { id=q.front(); q.pop(); vis[id]=0; for(edge *p=adj[id];p;p=p->next) { if(dis[id]*p->plu>dis[p->id]) { cnt[p->id]++; if(cnt[p->id]>n) return 1; dis[p->id]=dis[id]*p->plu; if(!vis[p->id]) { vis[p->id]=1; q.push(p->id); } } } } return 0; } int main() { string tmp,tmpa,tmpb; double num; int cas=0; cin>>n; while(n) { cas++; ok=0; ednum=0; for(int i=1;i<=n;i++) { adj[i]=NULL; } mymap.clear(); for(int i=1;i<=n;i++) { cin>>tmp; mymap.insert(make_pair(tmp,i)); } cin>>m; for(int i=1;i<=m;i++) { cin>>tmpa>>num>>tmpb; addEdge(mymap[tmpa],mymap[tmpb],num); } for(int i=1;i<=n;i++) { if(SPFA(i)) { ok=1; break; } } printf("Case %d: ",cas); if(ok) printf("Yes "); else printf("No "); cin>>n; } }