你们见过这么诡异的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>