By yusijia

Updated:

Contents

转：http://blog.csdn.net/chenguolinblog/article/details/8056444

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

分析：
1 题目要求的是经过一轮的转换之后，原来的比例能够大于1。比如原先的“美元：美元 
= 1：1”,最后要求能够达到“美元：美元 > 1”
2 假设dis[i][j]表示“i ： j”的比例，那么初始化dis[i][i] = - 1。
3 由于n最大为30，所以果断选择floyd算法。但是这里有个地方不同的是，这里并不是
要求最小而是求最大，所以应该要把“小于改成大于”
4 最后只要能够找到一种货币的兑换比例大于1即满足条件


#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 40

int n, m, flag;
double dis[MAXN][MAXN];
char ch[MAXN][MAXN];

double max(double a, double b)
{
    return a > b ? a : b;
}

void floyd()
{
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                dis[i][j] = max(dis[i][j], dis[i][k] * dis[k][j]);
            }
        }
    }
}

int main()
{
    //freopen("input.txt", "r", stdin);
    double val;
    int a, b, Case;
    char str1[MAXN], str2[MAXN];
    Case = 1;
    while(scanf("%d", &n) != EOF && n){
        flag = 0;
        for(int i = 1 ; i <= n ; i++){
           for(int j = 1 ; j <= n ; j++)
              dis[i][j] = -1;
        }
        for(int i = 1; i <= n; i++)
            scanf("%s", ch[i]);
        scanf("%d", &m);
        for(int i = 1; i <= m; i++){
            scanf("%s %lf %s", str1, &val, str2);
            //printf("%f\n", val);
            for(int i = 1; i <= n; i++){
                if(!strcmp(str1, ch[i])){ //找到这个单词
                    a = i;
                }
                if(!strcmp(str2, ch[i])){
                    b = i;
                }
            }
            //printf("%f %f\n", dis[a][b], val);
            if(dis[a][b] < val)
                dis[a][b] = val;  //a单词转换为b单词的转换率为val
        }
        floyd();
        for(int i = 1; i <= n; i++)if(dis[i][i] > 1.0){
            flag = 1;
            break;
        }
        if(flag)
            printf("Case %d: Yes\n" , Case++);
        else
            printf("Case %d: No\n" , Case++);

    }
    return 0;
}
Contents