当前位置: 代码迷 >> 综合 >> POJ 2240 - Arbitrage(map + SPFA判正环)
  详细解决方案

POJ 2240 - Arbitrage(map + SPFA判正环)

热度:35   发布时间:2024-02-19 20:21:47.0

Input

套利是指利用货币汇率的差异,将一种货币的一个单位转换为同一货币的多个单位。例如,假设1美元买0.5英镑,1英镑买10.0法国法郎,1法国法郎买0.21美元。然后,通过兑换货币,聪明的交易者可以从1美元开始,购买0.5 x 10.0 x 0.21 = 1.05美元,获得5%的利润。
您的工作是编写一个程序,以货币汇率列表作为输入,然后确定是否可能进行套利。

Output

输入将包含一个或多个测试用例。每个测试用例的第一行有一个整数n (1<=n<=30),表示不同货币的数量。接下来的n行每一行都包含一种货币的名称。名称中不会出现空格。下一行包含一个整数m,表示接下来的表的长度。最后的m行分别包含源货币的名称ci、表示从ci到cj的汇率的实数rij和目标货币的名称cj。没有出现在表格中的交易是不可能的。

测试用例通过空行彼此分开。对于n,输入以0(0)的值结束。

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 ,表示有 n 个币种,接下来输入m种转换方式,每种输入币种a,汇率c 和币种b,说明a -> b 的汇率是 b,依照题意,1英镑买10.0法国法郎,1法国法郎买0.21美元。然后,通过兑换货币,聪明的交易者可以从1美元开始,购买0.5 x 10.0 x 0.21 = 1.05美元,判断是否可以通过货币转换来实现套现。

解题思路:

抽象成图论问题,套现即找变大环,因为题目没有指定手中现有的货币,所以从1 - n 依次跑spfa判正环即可,建图的时候注意一下,这里输入的是字符串,通过map映射一下 ,映射成地图下标,再跑spfa即可。

Code:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define lowbit(x) x & (-x)using namespace std;typedef long long ll;
typedef pair<int, int> pii;const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 1e3 + 50;
const int M = 1e4 + 50;int h[N], ne[M], e[M], idx;
int n, m;
double dis[N], w[M];
int cnt[N];
bool vis[N];void add(int a, int b, double c)
{
    e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx++;
}void init()//多组输入,注意初始化
{
    idx = 0;memset(h, -1, sizeof h);
}
bool spfa(int s)//依次跑spfa判变大环
{
    queue<int > q;for (int i = 1; i <= n; i ++){
    dis[i] = 0;vis[i] = false;}q.push(s);vis[s] = true;dis[s] = 1;while (!q.empty()){
    int t = q.front();q.pop();vis[t] = false;for (int i = h[t]; ~i; i = ne[i]){
    int j = e[i];if (dis[t] * w[i] > dis[j]){
    dis[j] = dis[t] * w[i];cnt[j] = cnt[t] + 1;if (cnt[j] >= n) return true;if (!vis[j]){
    q.push(j);vis[j] = true;}}}}return false;
}int main()
{
    int c = 1;while (scanf("%d", &n) && n){
    init();map<string, int> mp;string s;for (int i = 1; i <= n; i ++)//借助map映射成整数下标{
    cin >> s;mp[s] = i;}scanf("%d", &m);while (m --){
    string a, b;double c;cin >> a >> c >> b;add(mp[a], mp[b], c);//建图的过程}bool flag = false;for (int i = 1; i <= n; i ++){
    memset(cnt, 0, sizeof cnt);flag = spfa(i);if (flag) break;}printf("Case %d: %s\n", c ++, flag ? "Yes" : "No");}return 0;
}