#include <iostream>
using namespace std;
#include <string.h>
#include <stdio.h>
const int size = 40;
char name[size][100];
int times;
#define max(a,b) a>b?a:b
class poj2240
{
private:
        double map[size][size];
public:
       int n;
       int m;
       void init();
       void input();
       void Foldy();
       void judge();
       int position(char str[]);
              
};

int poj2240::position(char str[])
{
    for(int index=1;index<=n;index++)
    if(!strcmp(name[index],str))
    return index;
}

void poj2240::init()
{
     int index;
     for(index=1;index<=n;index++)
     cin>>name[index];
     for(int i=1;i<=n;i++)
     {
             for(int j=1;j<=n;j++)
             map[i][j]=1.0;
     }
}

void poj2240::input()
{
     cin>>m;
     char str1[100],str2[100];
     int s,e;
     double w;
     for(int k=1;k<=m;k++)
     {
             cin>>str1>>w>>str2;
             s=position(str1);
             e=position(str2);
             map[s][e]=w;
     }
}
void poj2240::Foldy()
{
    for(int k=1;k<=n;k++)
    {
            for(int i=1;i<=n;i++)
            {
                    for(int j=1;j<=n;j++)
                   {
                            map[i][j]=max(map[i][j],map[i][k]*map[k][j]);
                   }
            }
    }
}

void poj2240::judge()
{
     int f=0;
     for(int k=1;k<=n;k++)
     if(map[k][k]>1)
     f=1;
     if(f)
     printf("Case %d: Yes",times++);
     else
     printf("Case %d: No",times++);
     printf("\n");
}

int main()
{
    poj2240 t;
    times=1;
    while(cin>>t.n)
    {
    if(!t.n)
    break;
    t.init();
    t.input();
    t.Foldy();
    t.judge();
    }  
    //system("pause");   
	return 1;
}

• Re:我的代码！flody的算法！ (87) wyjbupt 2012-11-14 23:05:14
  • Re:我的代码！flody的算法！ (13) zhanggt1994 2013-05-18 00:37:43