你们见过这么诡异的FLOYD吗？
先上题。
[Description]
货币的汇率存在差异。比如，如果1美元购买0.5英镑，1英镑买10法郎。而1法国法郎买0.21美元。然后，通过转换货币，一个聪明的交易者能够从1美元买0.5 * 10 * 0.21 = 1.05美元，获利5%。
你的任务是写一个程序，以一个货币汇率列表的作为输入，然后确定能不能获利。
[Intput]
输入包括多组測试数据，每组数据第一行一个数n(1<=n<=30)，表示有n中货币，接下来n行。每行一种货币名称，名称内不会出现空格，接下来一行一个整数m，然后是m行，每行包括三部分Si,Rij,Sj，表示货币Si兑换成Sj的汇率为Rij。
每组数据用一个空行隔开。当n==0时，结束输入。
[Output]
对于每组数据输出一个”Case i: Yes”或”Case i: No”表示第i组数据是否可行。
[Sample Input]
3
USDollar
BritishPound
FrenchFranc
3
USDollar 0.5 BritishPound
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar
3
USDollar
BritishPound
FrenchFranc
6
USDollar 0.5 BritishPound
USDollar 4.9 FrenchFranc
BritishPound 10.0 FrenchFranc
BritishPound 1.99 USDollar
FrenchFranc 0.09 BritishPound
FrenchFranc 0.19 USDollar
0
[Sample Onput]
Case 1: Yes
Case 2: No
乍一看好像是数学题，事实上嘛——————是图论（相信大家都看出来了吧）。
把汇率当做边，货币当做点。
FLOYD就好了嘛。
<span style="color:#660000;"><span style="font-size:18px;">for(int k=1;k<=n;k++)</span><span style="font-size:14px;">
</span><span style="font-size:18px;">for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(i==j || i==k || j==k) continue;
if(dis[i][j]<dis[i][k]*dis[k][j])
{
dis[i][j]=dis[i][k]*dis[k][j];
}
}</span></span>
特别注意此题的转移方程：汇率什么的当然是要乘咯。
注意：此题千万不能排除自环（我下意识的代码让我调了几个小时），即自己换自己汇率大于1（这尼玛不科学！）
<span style="color:#3366ff;background-color: rgb(102, 255, 153);">#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m;
double dis[35][35];
char name[35][3110];
char tmp[3110];
int ansnum=0; int main()
{
while(1)
{
scanf("%d",&n);
if(n==0) break;
memset(name,0,sizeof(name));
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j]=0.0;
for(int i=1;i<=n;i++) scanf("%s",name[i]);
scanf("%d",&m);
int u,v;
double w;
for(int i=1;i<=m;i++)
{
memset(tmp,0,sizeof(tmp));
scanf("%s",tmp);
for(int j=1;j<=n;j++)
{
if(strcmp(tmp,name[j])==0)
{
u=j;
break;
}
}
scanf("%lf",&w);
memset(tmp,0,sizeof(tmp));
scanf("%s",tmp);
for(int j=1;j<=n;j++)
{
if(strcmp(tmp,name[j])==0)
{
v=j;
break;
}
}
dis[u][v]=max(dis[u][v],w);
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(i==j || i==k || j==k) continue;
if(dis[i][j]<dis[i][k]*dis[k][j])
{
dis[i][j]=dis[i][k]*dis[k][j];
}
}
int ok=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
//if(i==j) continue;这句千万不能要
if(dis[i][j]*dis[j][i]>1.0)
{
ok=1;
}
if(ok) break;
}
if(ok) break;
}
printf("Case %d: ",++ansnum);
if(ok) printf("Yes\n");
else printf("No\n");
}
return 0;
}</span>