d[i]代表从起点出发可以获得最多的钱数，松弛是d[v]=r*d[u]，求最长路，看有没有正环
然后这题输入有毒，千万别用cin 因为是大输入，组数比较多，然后找字符串用strcmp就好，千万不要用map
这题刚开始我T了（用的map），还以为组数很多卡spfa呢，然后我上网看了看都是floyd的，然后我用floyd写了一发，891ms过了
然后我感觉spfa的复杂度也不是很大，就是看有没有正环，所以我觉得可能是map+cin的锅，然后改了一发，用的spfa，47ms过
真是，算了，实质是本蒟蒻经验不足（其实也不是没做过卡输入的）
这是map+cin+floyd
#include<cstdio> #include<cstring> #include<queue> #include<cstdlib> #include<algorithm> #include<vector> #include<iostream> #include<string> #include<cmath> #include<map> using namespace std; typedef long long LL; const int N=35; const int INF=0x3f3f3f3f; map<string,int>mp; double d[N][N]; int n,m; bool fun(){ for(int k=1;k<=n;++k) for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) d[i][j]=max(d[i][j],d[i][k]*d[k][j]); for(int i=1;i<=n;++i) if(d[i][i]>1)return true; return false; } int main(){ int cas=0; while(~scanf("%d",&n),n){ mp.clear(); for(int i=1;i<=n;++i){ string t; cin>>t; mp[t]=i; } memset(d,0,sizeof(d)); for(int i=1;i<=n;++i) d[i][i]=1; scanf("%d",&m); while(m--){ string x,y; double r; cin>>x>>r>>y; d[mp[x]][mp[y]]=r; } printf("Case %d: ",++cas); if(fun())printf("Yes "); else printf("No "); } }
这是strcmp+spfa（推荐看这个）
#include<cstdio> #include<cstring> #include<queue> #include<cstdlib> #include<algorithm> #include<vector> #include<iostream> #include<string> #include<cmath> #include<map> using namespace std; typedef long long LL; const int N=35; const int INF=0x3f3f3f3f; struct Edge{ int v,next; double r; }edge[N*N]; int n,m,head[N],tot,cnt[N]; void add(int u,int v,double r){ edge[tot].v=v; edge[tot].r=r; edge[tot].next=head[u]; head[u]=tot++; } bool inq[N]; double d[N]; queue<int>q; bool spfa(int s){ for(int i=1;i<=n;++i) d[i]=cnt[i]=inq[i]=0; d[s]=1,++cnt[s],inq[s]=true; while(!q.empty())q.pop(); q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); inq[u]=false; for(int i=head[u];~i;i=edge[i].next){ int v=edge[i].v; if(d[u]*edge[i].r>d[v]){ d[v]=d[u]*edge[i].r; if(!inq[v]){ inq[v]=true; if(++cnt[v]>n)return true; q.push(v); } } } if(d[s]>1)return true; } return false; } char a[N][100]; int find(char *s){ for(int i=1;i<=n;++i) if(!strcmp(s,a[i]))return i; } int main(){ int cas=0; while(~scanf("%d",&n),n){ memset(head,-1,sizeof(head)),tot=0; for(int i=1;i<=n;++i) scanf("%s",a[i]); scanf("%d",&m); while(m--){ char s[100]; double r; scanf("%s%lf",s,&r); int u=find(s); scanf("%s",s); int v=find(s); add(u,v,r); } printf("Case %d: ",++cas); if(spfa(1))printf("Yes "); else printf("No "); } }