原题：点击打开链接
题意：给你一些货币，问你是否可以在兑换中获得利润。跟poj1860很像，题目链接：点击打开链接
刚开始用的数组邻接表建图，无限t，后来改成map才A掉。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <string> #include <queue> #include <vector> using namespace std; const int maxn=100; char s[maxn][maxn]; vector<int> map[maxn]; int cnt,next[maxn*2],n,vis[maxn],cnt1[maxn],in[maxn]; double dist[maxn],f[maxn][maxn]; int num(char *ss) { for(int i=0;i<n;i++) if(strcmp(ss,s[i])==0) return i; } int spfa(int u) { queue<int> q; memset(vis,0,sizeof(vis)); memset(dist,0,sizeof(dist)); memset(cnt1,0,sizeof(cnt1)); dist[u]=1.0; q.push(u);vis[u]=1;cnt1[u]++; while(!q.empty()) { int x=q.front(); q.pop();vis[x]=0; for(int i=0;i<map[x].size();i++) { int edge=map[x][i]; if(dist[edge]<dist[x]*f[x][edge]) { dist[edge]=dist[x]*f[x][edge]; if(!vis[edge]) { vis[edge]=1; q.push(edge); cnt1[edge]++; if(cnt1[edge]>=in[edge]) { return 1; } } } } } return 0; } int main() { int ans=1; while(scanf("%d",&n)!=EOF) { if(n==0) break; memset(s,0,sizeof(s)); memset(in,0,sizeof(in)); int flag=0; for(int i=0;i<n;i++) scanf("%s",s[i]); int m; scanf("%d",&m); cnt=0; memset(f,-1,sizeof(f)); // memset(dist,0,sizeof(dist)); for(int i=0;i<m;i++) { char s1[maxn],s2[maxn]; memset(s1,0,sizeof(s1)); memset(s2,0,sizeof(s2)); double r; scanf("%s %lf %s",s1,&r,s2); int a=num(s1),b=num(s2); //edge[cnt].u=a; f[a][b]=r; in[b]++; map[a].push_back(b); } printf("Case %d: ",ans++); for(int i=0;i<n;i++) { if(spfa(i)){ flag=1; break; } } if(flag) printf("Yes\n"); else printf("No\n"); } return 0; }
