hdu 1217 Arbitrage (最小生成树)

/************************************************************************/
/*     
        hdu  Arbitrage
        floyd求最短路径
        题目大意：floyd算法，求得两点之间最短距离，（u，v） = min( (u,v),(u,w)+(w,v) );

此题，是求其能够赚钱,即最大生成树，且过程是相乘的，公式：（ u, v） = max( (u,v), (u,w)*(w,v) );
*/
/************************************************************************/

#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;

#define MIN(a,b) a<b?a:b
#define MAX 0xfffffff

const int N = 31;
double maps[N][N];
int num,key;
map<string,int> hash_map;

void build_map()
{
    char name[20],name1[20];
    double rate;
    int m;
    for (int i = 1; i <= num; i++)
    {
        scanf("%s",name);
        hash_map[name] = i;
    }
    memset(maps,0,sizeof(maps));
    scanf("%d",&m);
    for (int i = 0; i < m; i++)
    {
        scanf("%s%lf%s",name,&rate,name1);
        maps[hash_map[name]][hash_map[name1]] = rate;
    }

}

void fload()
{
    for (int k = 1; k <= num; k++)
    {
        for (int i = 1; i <= num; i++)
        for (int j = 1; j <= num; j++)
        maps[i][j] = max(maps[i][j],maps[i][k] * maps[k][j]);
    }
    int j;
    for (j = 1; j <= num; j++)
    if (maps[j][j] > 1)break;
    if (j>num)printf("Case %d: No\n",key);
    else printf("Case %d: Yes\n",key);
    hash_map.clear();
}


int main()
{
    key = 0;
    while(scanf("%d",&num) && num != 0 )
    {
        key++;
        build_map();
        fload();
    }
    return 0;
}