poj-2240-Arbitrage（Bellman-ford算法練習 + Floyd算法練習）

Arbitrage

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 20761	Accepted: 8846

Description

Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 US Dollar buys 0.5 British pound, 1 British pound buys 10.0 French francs, and 1 French franc buys 0.21 US dollar. Then, by converting currencies, a clever trader can start with 1 US dollar and buy 0.5 * 10.0 * 0.21 = 1.05 US dollars, making a profit of 5 percent. 

Your job is to write a program that takes a list of currency exchange rates as input and then determines whether arbitrage is possible or not. 

Input

The input will contain one or more test cases. Om the first line of each test case there is an integer n (1<=n<=30), representing the number of different currencies. The next n lines each contain the name of one currency. Within a name no spaces will appear. The next line contains one integer m, representing the length of the table to follow. The last m lines each contain the name ci of a source currency, a real number rij which represents the exchange rate from ci to cj and a name cj of the destination currency. Exchanges which do not appear in the table are impossible. 

Test cases are separated from each other by a blank line. Input is terminated by a value of zero (0) for n.

Output

For each test case, print one line telling whether arbitrage is possible or not in the format "Case case: Yes" respectively "Case case: No".

Sample Input

3
USDollar
BritishPound
FrenchFranc
3
USDollar 0.5 BritishPound
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar

3
USDollar
BritishPound
FrenchFranc
6
USDollar 0.5 BritishPound
USDollar 4.9 FrenchFranc
BritishPound 10.0 FrenchFranc
BritishPound 1.99 USDollar
FrenchFranc 0.09 BritishPound
FrenchFranc 0.19 USDollar

0
      

Sample Output

Case 1: Yes

Case 2: No

題意：

已知n種貨币，以及m種貨币匯率及方式，問能否通過貨币轉換，使得财富增加。

題目連結：Arbitrage

解題思路：

目測是一條不錯的生财之道~~~（打住）

财富增加的話肯定是以同種貨币作比較，否則沒有意義，是以題意大緻可以變成在一個n個頂點的圖中能否找到一個正權環，這裡的正權環指财富增加，很明顯可用Bellman-ford 算法（專門解決存在環的最短路徑問題）。

Bellman-ford 算法：一個具有n個頂點的圖如果不存在環，則從頂點x,到頂點y，最多經過n-1條邊（要考慮連通性，每個頂點最多經過 1 次），是以 x 到 y 的最短路 最多經過 n - 1 次松弛操作（就是更新長度）就應該出現，如果第 n 次松弛還可以得到最優，那麼這個圖就肯定是存在環了（直接用Dijkstra 就無法得到最優的，環的存在會影響最優解是否存在）。

這裡給的頂點時貨币的英文名，為了友善簡潔，用map 将貨币名 與 編号一一對應

此題有多種解法，注意到頂點最大為30（限制很小，不愧是模闆練習題），可用Floyd算法求出整個圖的最短路，注意此處并不是真正的最短路，但通過插點，即 i -> j 能否改成 i -> k -> j 的路，就會把環給考慮至少一次，那麼對應的 path[i][i] 也就是本金肯定是增加的（相對于初值），為了友善，将本金設為 1 .

代碼；

Bellman_ford 實作：

//Bellman_ford
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>

using namespace std;
int n,m;
double dist[40];    //注意類型為 double
struct edge //邊的結構體,st為起點,ed為終點,rt為匯率
{
    int st,ed;
    double rt;
    edge(int sst,int eed,double rtt) : st(sst),ed(eed),rt(rtt) {}
    edge() {}
};

vector<edge> G;
map<string ,int> mp;

bool Bellman_ford(int v)
{
    memset(dist,0,sizeof(dist));
    dist[v] = 1;
    for(int j = 1;j < n;j++) {  // n - 1 次松弛操作
        for(int i = 0;i < G.size();i++) {
            int p1 = G[i].st,p2 = G[i].ed;
            if(dist[p2] < dist[p1] * G[i].rt) { //嘗試更新頂點 v 到 p2 的距離
                dist[p2] = dist[p1] * G[i].rt;
            }
        }
    }
    for(int i = 0;i < G.size();i++){
        int p1 = G[i].st,p2 = G[i].ed;
        if(dist[p2] < dist[p1] * G[i].rt) { //第 n 次松弛可以得到更優解，則存在環
            return true;    
        }
    }
    return false;
}

int main()
{
    int cas = 1;
    string s,ss;
    while(~scanf("%d",&n) &&n) {
        for(int i = 0;i < n;i++) {
            cin >> s;
            mp[s] = i; //貨币名 s 的頂點編号 為 i
        }
        cin >> m;
        string beg,ends;
        double r;
        G.clear();
        for(int i = 0;i < m;i++) {
            cin >> beg >> r >> ends;    //邊的資訊讀取
            G.push_back(edge (mp[beg] ,mp[ends] ,r) );
        }
        printf("Case %d: ",cas++);
        for(int i = 0;i < n;i++) { //枚舉所有開始的起點
            if(Bellman_ford(i)) {   //存在環
                cout << "Yes" << endl;
                //printf("bellman %d\n",i);
                break;
            }
            else if(i == n - 1)
                cout << "No" <<endl;
        }
    }
    return 0;
}
           

Floyd 算法：

//floyed
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>

using namespace std;
int n,m;
double dist[40][40];
map<string,int> money;

void init()
{
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < n;j++){
            if(i == j) dist[i][j] = 1;
            else dist[i][j] = 0;
        }
    }
}

void floyd()
{
    for(int k = 0;k < n;k++) {
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < n;j++) {
                if(dist[i][j] < dist[i][k] * dist[k][j])
                    dist[i][j] = dist[i][k] * dist[k][j];
            }
        }
    }
}

int main()
{
    int cas = 1;
    string s,ss;
    double r;
    while(~scanf("%d",&n) &&n) {
        init();
        for(int i = 0;i < n;i++) {
            cin >> s;
            money[s] = i;
        }
        cin >> m;

        for(int i = 0;i < m;i++) {
            cin >> s >> r >> ss;
            dist[money[s] ][money[ss] ] = r;
        }
        floyd();
        printf("Case %d: ",cas++);
        for(int i = 0;i < n;i++) {
            if(dist[i][i] > 1) {
                cout << "Yes" << endl;
                break;
            }
            else if(i == n - 1)
                cout << "No" <<endl;
        }
    }
    return 0;
}