跟前天做的那個題目有點共同之處 都是把FLOYD換了一種用法
在此題中就是更新邊權乘積到最大值 最后找有沒有邊權乘積大于一的環
想到了就很EASY～
代碼如下：
? ???
#include <stdio.h>
#include <string>
#include <iostream>
using namespace std;
char str[31][31],curr1[31],curr2[31];
double change[31][31];
int find(int n,char st[])
{
??? int i;
??? for(i=1;i<=n;i++)
??? {
??? if(!strcmp(str[i],st))
??? return i;
?? }
?? return -1;
}
void FLOYD(int n,double change[][31])
{
???? int i,j,k;
???? for(i=1;i<=n;i++)
????? for(j=1;j<=n;j++)
?????? for(k=1;k<=n;k++)
?????? {
???????? double tmp=change[j][i]*change[i][k];
???????? if(tmp>change[j][k])
???????? change[j][k]=tmp;
?????? }
}
int main()
{
??? int m,n,i,flag,t=0;
??? double ratio;
??? while(scanf("%d",&n)!=EOF)
??? {
????? if(n==0) break;?????????????????????????
????? t++;
????? flag=0;
????? memset(change,0,sizeof(change));
????? for(i=1;i<=n;i++)
?????? scanf("%s",str[i]);
?????
????? scanf("%d",&m);
?????
????? for(i=1;i<=m;i++)
????? {
?????? cin>>curr1>>ratio>>curr2;
?????? change[find(n,curr1)][find(n,curr2)]=ratio;
????? }
?????
????? FLOYD(n,change);
?????
????? for(i=1;i<=n;i++)
????? {
??????? if(change[i][i]>1)
??????? {
???????? flag=1;
???????? break;
??????? }
????? }
?????
??????? if(flag)
????????????? printf("Case %d: Yes\n",t);
???????? else
????????????? printf("Case %d: No\n",t);
??? }
???
}