POJ 2240 Arbitrage（Floyed-Warshall算法）

题意：给出n种货币，m种兑换比率（一种货币兑换为另一种货币的比率），判断测试用例中套汇是否可行。（套汇的意思就是在经过一系列的货币兑换之后，是否可以获利。例如：货币i→货币j→货币i，这样兑换后，是否可以获利，即比率是否>1）。举个例子理解套汇：假设，1美元买10人民币（比率为10），10人民币买100美元（比率为10）。这就是套汇，总比率=10*10=100，100>1，所以可以获利。

思路：Floyed-Warshall算法，枚举所有的货币之间的兑换比率，最后若存在一种回路且回路比率>1的话，则套汇可行。

课本代码：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int maxn=50;//货币种类上限

const int maxl=1005;//货币名字长度上限

char str[maxn][maxl],stra[maxl],strb[maxl];//货币种类数组str，源货币stra，目标货币strb。

long double dist[maxn][maxn];//比率矩阵

int n,m;

int find(char *_str){//查找货币的序号i

	for(int i=1;i<=n;i++)

		if(strlen(_str)==strlen(str[i])&&strcmp(_str,str[i])==0) return i;

		return 0;

}

int main(){

	while(scanf("%d",&n)&&n){

		static int cnt=0;

		int i,j,k;

		for(i=1;i<=n;i++)//初始化货币比率

			for(j=1;j<=n;j++)

				dist[i][j]=0;

			for(i=1;i<=n;i++)//0不用，作为未知货币。

				scanf("%s",str[i]);

			scanf("%d",&m);

			for(i=1;i<=m;i++){

				double w;

				scanf("%s %lf %s",stra,&w,strb);

				dist[find(stra)][find(strb)]=w;

			}

			for(k=1;k<=n;k++)//枚举中间节点k

				for(i=1;i<=n;i++)//枚举互不相同的节点对(i,j)

					for(j=1;j<=n;j++)

						if(i!=j&&j!=k&&k!=i)

							if(dist[i][k]*dist[k][j]>dist[i][j])

								dist[i][j]=dist[i][k]*dist[k][j];

			bool flag=0;//标志初始化

			for(i=1;i<=n;i++)//枚举每种货币

				for(j=1;j<=n;j++)//枚举中间货币

					if(dist[i][j]*dist[j][i]>1)//如果比率>1，则套汇可行

						flag=1;

			printf("Case %d: %s\n",++cnt,flag?"Yes":"No");

	}

	return 0;

}