2240:Arbitrage

keyword

Warshall-Floyd　C++

概要

様々な通貨の為替レートが与えられる。ただし、A->BとB->Aのレートは独立である。このとき、為替によって利益を上げることができるかどうか判定する問題。
グラフの問題だと思うと、自分自身に帰る倍率1以上のルートが存在すればよい。多分普通の最短経路の問題で負の閉路を検出する問題と同じなので、実装量の少ないWarshall-Floydで書いたら無事通った。正当性の証明はしていない。

int main(){

    double graph[40][40];
    double rate;
    map<string, int> nameTable;
    char from[102], to[102];
    int i, j, k, n, m, cnt=1;

    while(scanf("%d\n",&n)){
        if(!n) break;
        REP(i,n)REP(j,n) graph[i][j] = 0.0;
        REP(i,n){
            scanf("%s\n",from);
            nameTable[string(from)] = i;
        }
        scanf("%d\n",&m);
        REP(i,m){
            scanf("%s %lf %s\n",from, &rate, to);
            graph[nameTable[string(from)]][nameTable[string(to)]] = rate;
        }

        REP(k,n)REP(i,n)REP(j,n){
            graph[i][j] = max(graph[i][j], graph[i][k]*graph[k][j]);
        }

        REP(i,n)if(graph[i][i] > 1.0+EPS) break;
        printf("Case %d: %s\n", cnt++, (i==n?"No":"Yes"));
    }

    return 0;
}