GroupBlog

题意

给定多种货币之间的兑换关系，问是否可以套利

思路

可以判断正环是否存在，或者直接floyd后判断有没有v[i][i] > 1，有则说明可以套利
因为数据量很小，所以直接floyd
输入数据存在 a x a，即a和a之间的汇率(好坑啊，害我wrong那么多次)

代码

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 35;
const int MAX = 0x3f3f3f3f;
double v[N][N];
char s[N][50];

bool floyd(int n)
{
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            for(int k=0; k<n; k++)
                if(v[j][k] < v[j][i]*v[i][k])
                    v[j][k] = v[j][i]*v[i][k];
    for(int i=0; i<n; i++)
        if(v[i][i] > 1)
            return true;
    return false;
}

int main()
{
    int n, m, T = 1;
    while(~scanf("%d", &n) && n)
    {
        memset(v, 0, sizeof(v));
        for(int i=0; i<n; i++)
        {
            scanf("%s", s[i]);
            v[i][i] = 1;
        }
        scanf("%d", &m);
        for(int i=0; i<m; i++)
        {
            char a[50], b[50];
            int x, y;
            double c;
            scanf("%s%lf%s", a, &c, b);
            for(int j=0; j<n; j++)
            {
                if(strcmp(s[j], a) == 0)
                    x = j;
                if(strcmp(s[j], b) == 0)
                    y = j;
            }
            v[x][y] = c;
        }
        printf("Case %d: ", T++);
        if(floyd(n))
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}