POJ2240

floyd

题意:给定一些money以及之间的转化,询问最后能不能让某种money升值

View Code
 1 #include<stdio.h>
 2 #include<map>
 3 #include<string>
 4 #include<iostream>
 5 using namespace std;
 6 const int maxn = 105;
 7 map<string,int>mp;
 8 double mat[ maxn ][ maxn ];
 9 double fmax( double a ,double b ){
10     return a>b?a:b;
11 }
12 int main(){
13     int n;
14     int cnt=1;
15     while( scanf("%d",&n)==1,n ){
16         string s;
17         for( int i=1;i<=n;i++ ){
18             cin>>s;
19             mp[ s ]=i;
20         }
21         int m;
22         scanf("%d",&m);
23         string s1,s2;
24         double tmp;
25         for( int i=0;i<maxn;i++ )
26             for( int j=0;j<maxn;j++ )
27                 if( i==j )
28                     mat[ i ][ j ]=1.0;
29                 else
30                     mat[ i ][ j ]=0.0;
31         for( int i=1;i<=m;i++ ){
32             cin>>s1;
33             cin>>tmp;
34             cin>>s2;
35             mat[ mp[ s1 ] ][ mp[ s2 ] ]=tmp;
36         }
37         for( int k=1;k<=n;k++ ){
38             for( int i=1;i<=n;i++ ){
39                 for( int j=1;j<=n;j++ ){
40                     if( mat[i][k]>0 && mat[k][j]>0 ){
41                         mat[i][j]=fmax( mat[i][j],mat[i][k]*mat[k][j]);
42                     }
43                 }
44             }
45         }
46         int flag=-1;
47         for( int i=1;i<=n;i++ )
48             if( mat[i][i]>1 ){
49                 flag=1;
50                 break;
51             }
52         printf("Case %d: ",cnt++);
53         if( flag==1 )printf("Yes\n");
54         else printf("No\n");
55     }
56     return 0;
57 }
keep moving...
原文地址:https://www.cnblogs.com/xxx0624/p/2829601.html