巢穴

about:blank

P2240

   还是floyd...
   orz..最短路切完了.
  
#include <iostream>
#include <string>
#include <map>
#include <fstream>
#include <math.h>
using namespace std;
ifstream fin("t2240.in");
map<string,int> hash;

#define eps 1e-8
const int MAXN=31;
int n,m;
double edge[MAXN][MAXN];
//string name[MAXN];
int main()
{
    int num=0;
    while(1)
    {
      cin>>n;
      if (0==n) break;
      for (int i=1;i<=n;i++)
      {
          string str;
          cin>>str;
          hash.insert(make_pair<string,int>(str,i));
          //name[i]=str;
      }
      cin>>m;
      memset(edge,1,sizeof(edge));
      for (int i=1;i<=m;i++)
      {
          string name1,name2;
          double r;
          cin>>name1>>r>>name2;
          edge[hash[name1]][hash[name2]]=r; 
      }
      for (int k=1;k<=n;k++)
       for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        {
            double temp=edge[i][k]*edge[k][j];
            if (edge[i][j]+eps<temp)
            {
              edge[i][j]=temp;
            }
        }
      bool ok=true;
      for (int i=1;i<=n;i++)
       if (edge[i][i]+eps<1||fabs(edge[i][i]-1)<eps)
       {
         ok=false;break;
       } 
     if (ok)
     {
      cout<<"Case "<<++num<<": Yes"<<endl;
     }
     else
      cout<<"Case "<<++num<<": No"<<endl;
      
     //system("pause"); 
    }
    
    return 0;
}

posted on 2009-10-05 12:17 Vincent 阅读(160) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理