zoj 1092 Arbitrage

题目大意是有n个国家之间的汇率，问是否存在从一个国家出发回到该国家后汇率乘积大于一，即套汇。

可以用bellman做，因为是回路，所以要递推n次（多于n次无意义，因为若存在套汇，n次就知道了）。

也可以用floyd算法，最后判断lowdist[ i ][ i ]即可。

#include <stdio.h>
#include <string.h>
int n,m,flag;
double maxdist[50];
char name[50][20],a[20],b[20];
struct exchange
{
	int ci;
	int cj;
	double cij;
}ex[1000];
void bellman(int u)
{
	int i,j;
	memset(maxdist,0,sizeof(maxdist));
	maxdist[u]=1;
	for(i=1;i<=n;i++)
	{
		for(j=0;j<m;j++)
		{
			if(maxdist[ex[j].cj]<maxdist[ex[j].ci]*ex[j].cij)
				maxdist[ex[j].cj]=maxdist[ex[j].ci]*ex[j].cij;
		}
	}
	if(maxdist[u]>1.0)
		flag=1;
}


int main()
{
	int i,j,k,sum=0;
	double x;
	while(1)
	{
		flag=0;
		scanf("%d",&n);
		if(n==0)
			break;
		for(i=0;i<n;i++)
			scanf("%s",name[i]);
		scanf("%d",&m);
		for(i=0;i<m;i++)
		{
			scanf("%s %lf %s",a,&x,b);
			for(j=0;strcmp(a,name[j]);j++);
			for(k=0;strcmp(b,name[k]);k++);
			ex[i].ci=j;
			ex[i].cij=x;
			ex[i].cj=k;
		}
		for(i=0;i<n;i++)
		{
			bellman(i);
			if(flag)
				break;
		}
		sum+=1;
		if(flag)
			printf("Case %d: Yes
",sum);
		else
			printf("Case %d: No
",sum);
	}
	return 0;
}