Victordu

跟前天做的那个题目有点共同之处 都是把FLOYD换了一种用法
在此题中就是更新边权乘积到最大值 最后找有没有边权乘积大于一的环
想到了就很EASY～

代码如下：
/**********************
Author: WHU_Victordu
Created Time: 2007-12-30
File Name: pku2240.cpp
  Description: 
   **************************/
#include <stdio.h>
#include <string>
#include <iostream>

using namespace std;

char str[31][31],curr1[31],curr2[31];
double change[31][31];

int find(int n,char st[])
{
    int i;
    for(i=1;i<=n;i++)
    {
    if(!strcmp(str[i],st))
    return i;
   }
   return -1;
}

void FLOYD(int n,double change[][31])
{
     int i,j,k;
     for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
       for(k=1;k<=n;k++)
       {
         double tmp=change[j][i]*change[i][k];
         if(tmp>change[j][k])
         change[j][k]=tmp;
       }
}

int main()
{
    int m,n,i,flag,t=0;
    double ratio;
    while(scanf("%d",&n)!=EOF)
    {
      if(n==0) break;                         
      t++;
      flag=0;
      memset(change,0,sizeof(change));
      for(i=1;i<=n;i++)
       scanf("%s",str[i]);
     
      scanf("%d",&m);
     
      for(i=1;i<=m;i++)
      {
       cin>>curr1>>ratio>>curr2;
       change[find(n,curr1)][find(n,curr2)]=ratio;
      }
     
      FLOYD(n,change);
     
      for(i=1;i<=n;i++)
      {
        if(change[i][i]>1)
        {
         flag=1;
         break;
        }
      }
     
        if(flag)
              printf("Case %d: Yes\n",t);
         else
              printf("Case %d: No\n",t);
    }
   
}