hdu 1217 Arbitrage (最小生成树)-白红宇

hdu 1217 Arbitrage (最小生成树)

阅读量：5889 次

发布时间：2019-06-19

本文共 1226 字，大约阅读时间需要 4 分钟。

题目：

/************************************************************************//*             hdu  Arbitrage        floyd求最短路径        题目大意：floyd算法，求得两点之间最短距离，（u，v） = min( (u,v),(u,w)+(w,v) ); 　　　　此题，是求其能够赚钱,即最大生成树，且过程是相乘的，公式：（ u, v） = max( (u,v), (u,w)*(w,v) );*//************************************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           using namespace std;#define MIN(a,b) a
           
             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;}