POJ-2240 Floyd的变化..

原本想再接再励做SPFA的....搜到这题~~结果用Floyd水掉了...题目的意思是说国家国家之间的货币有不同的汇率~~问有没有可能让钱从一个国家开始经过一系列国家汇率转换..最终回到手中钱变多了...

Floyd在更新的时候改一下..因为要钱越多越好~~所以就不是取最小值~~而是最大值~~并且在更新时~~线段与枚举的中心点不是相加而是相乘...最后判断 mar[ i ] [ i ] 中有无大于1的..

还有初始化的时候..mar [ i ][ i ] 自己到自己的初始化为1.... 其他的初始化为一个负数就可以了~~

Program:

#include<iostream>
#include<algorithm>
#include<map> 
#include<stdio.h>
#include<string.h>
using namespace std;  
map<string,int> mymap;
string a[40];
char s[1001];
int n,m,i,j,t;
double mar[40][40];
bool Floyd()
{ 
    int i,j,k;
    for (k=1;k<=n;k++)
      for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
          if (mar[i][j]<mar[i][k]*mar[k][j])
            mar[i][j]=mar[i][k]*mar[k][j];
    for (i=1;i<=n;i++) 
      if (mar[i][i]-1>0.0001) return true;
    return false;        
}
int main()
{ 
    t=0;
    while (~scanf("%d",&n))
    {
        if (!n) break; 
        mymap.clear();
        for (i=1;i<=n;i++)
        {
            scanf("%s",s);
            a[i]=s;
            mymap[a[i]]=i;
        }
        scanf("%d",&m);
        for (i=1;i<=n;i++)
         for (j=1;j<=n;j++) mar[i][j]=-1000000;
        for (i=1;i<=n;i++) mar[i][i]=1;
        for (i=1;i<=m;i++) 
        {
            int x,y;
            double k;
            scanf("%s",s);
            a[0]=s;
            x=mymap[a[0]];
            scanf("%lf",&k);    
            scanf("%s",s);
            a[0]=s;
            y=mymap[a[0]];      
            mar[x][y]=k;                  
        }     
        t++;
        printf("Case %d: ",t);   
        if (Floyd()) printf("Yes\n"); else printf("No\n");
    }
    return 0;   
}