首页 > ACM题库 > HDU-杭电 > HDU 1217 Arbitrage-最短路径-[解题报告] C++
2013
12-04

HDU 1217 Arbitrage-最短路径-[解题报告] C++

Arbitrage

问题描述 :

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.

输入:

The input file 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.

输出:

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

样例输入:

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

样例输出:

Case 1: Yes
Case 2: No

题意:类似 套汇,问货币轮流转移一圈会不会有盈利

分析:有spfa算法,这里因为数据量比较小所以用了floyd

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define re(i,n) for(int i=0;i<n;i++)
#define re1(i,n) for(int i=1;i<=n;i++)
#define clr(x,y) memset(x,y,sizeof(x))
#define inf (1<<29)
const int maxn =33;
int n , m;
double G[maxn][maxn] , diss;
char ch[maxn][maxn] , ch1[maxn] , ch2[maxn];
void floyd() {
    re(k,n) re(i,n) re(j,n) if(G[i][j] < G[i][k]*G[k][j])
        G[i][j] = G[i][k] * G[k][j];
}
int main() {
    int cas = 1;
    while(~scanf("%d",&n) && n) {
        clr(G,0);
        re(i,n) scanf("%s",ch[i]);
        scanf("%d",&m);
        while(m--) {
            int u , v;
            scanf("%s%lf%s",ch1,&diss,ch2);
            re(i,n) if(strcmp(ch[i],ch1) == 0) { u = i; break; }
            re(i,n) if(strcmp(ch[i],ch2) == 0) { v = i; break; }
            G[u][v] = diss;
        }
        floyd();
        int flag = 0;
        re(i,n) if(G[i][i] > 1) { flag = 1; break; }
        if(flag) printf("Case %d: Yes\n",cas++);
        else printf("Case %d: No\n",cas++);
    }
    return 0;
}

  1. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

  2. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.