//使用Floyd的變形實(shí)現(xiàn)
//這就是個套匯的問題，可以用Floyd求最大環(huán)，然后判斷是不是大于1。
#include <cstdio>
#include <string>
#include <map>
using namespace std;
map<string,int> MAP;
double value[31][31];
double rate;
double tempfloat;
int main()
{
??? int i,j,k,n,m;
??? int count=1;
??? char temp[100],temp1[100];
??? while(scanf("%d",&n))
??? {
??????? if(n==0)
??????????? break;
??????? MAP.clear();??//清空map
??????? memset(value,0,sizeof(value));?//double類型的二位數(shù)組也可用memset進(jìn)行初始化
??????? for(i=1;i<=n;i++)
??????? {
??????????? scanf("%s",temp);
??????????? MAP[(string)temp]=i;
??????? }
??????? scanf("%d",&m);
??????? for(i=1;i<=m;i++)
??????? {
??????????? scanf("%s %lf %s",temp,&rate,temp1);
??????????? value[MAP[(string)temp]][MAP[(string)temp1]]=rate;
??????? }
??//此處使用Floyd算法實(shí)現(xiàn)
??????? for(k=1;k<=n;k++)
????????? for(i=1;i<=n;i++)
??????????? for(j=1;j<=n;j++)
??????????? {
??????????????? tempfloat=value[i][k]*value[k][j];
??????????????? if(tempfloat>value[i][j])?//此處注意與傳統(tǒng)的Floyd算法不同,此處的松弛操作是往大的方向
??????????????????????? value[i][j]=tempfloat;
??????????? }
??????? for(i=1;i<=n;i++)
??????????? if(value[i][i]>1)?//判斷環(huán)
??????????? {
??????????????? printf("Case %d: Yes\n",count++);
??????????????? break;
??????????? }
??????? if(i==n+1)
??????? printf("Case %d: No\n",count++);
??? }
}

轉(zhuǎn)載于:https://www.cnblogs.com/north_dragon/archive/2010/04/28/1723349.html

總結(jié)

以上是生活随笔為你收集整理的POJ 2240题（Floyd）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。