每次都以一个点为源点用一次bellman_ford求最长路，有正权回路，则套汇成功，否则失败。
#include<iostream> using namespace std; #include<cstdio> #include<cstdlib> #define N 35 #define max_int 0xffffff #define eps 1e-8 struct edge { int u,v; double r; }; edge e[N*N]; int k; double dist[N]; char name[N][N]; int cmp(const void *a,const void *b) { return strcmp((char *)a,(char *)b); } int mysearch(char s[][N],char key[],int n) { int mid,left=1,right=n; while(left<=right) { mid=(left+right)/2; if(strcmp(key,s[mid])==0) return mid; else if(strcmp(key,s[mid])>0) left=mid+1; else right=mid-1; } } void add_edge(int u,int v,double r) { e[k].u=u,e[k].v=v,e[k].r=r; k++; } bool bellman(int s,int n) { int i,j; bool flag; for(i=1;i<=n;i++) dist[i]=-max_int; dist[s]=1; for(i=1;i<n;i++) { flag=false; for(j=0;j<k;j++) if(dist[e[j].u]*e[j].r+eps>dist[e[j].v]) { dist[e[j].v]=dist[e[j].u]*e[j].r+eps; flag=true; } if(!flag) break; } for(j=0;j<k;j++) if(dist[e[j].u]*e[j].r+eps>dist[e[j].v]) return true; if(dist[s]>1+eps) return true; else return false; } int main() { int n,m,u,v,i,ca=0; char line1[N],line2[N]; double r; while(scanf("%d",&n),n) { ca++; for(i=1;i<=n;i++) scanf("%s",name[i]); qsort(name+1,n,sizeof(name[1]),cmp); scanf("%d",&m); k=0; for(i=1;i<=m;i++) { scanf("%s%lf%s",line1,&r,line2); u=mysearch(name,line1,n); v=mysearch(name,line2,n); add_edge(u,v,r); } for(i=1;i<=n;i++) if(bellman(i,n)) { printf("Case %d: Yes/n",ca); break; } if(i>n) printf("Case %d: No/n",ca); } return 0; }
