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;
}