当前位置：首页 > news >正文

UVa 436 Arbitrage (II)

news 2026/6/9 19:22:59

题目描述

题目要求判断是否存在套利机会。给定若干种货币和它们之间的兑换汇率，判断是否存在一种兑换序列，使得从某种货币出发，经过一系列兑换后，最终得到多于原来数量的同一货币。

输入格式

输入包含多个测试用例。每个测试用例格式如下：

第一行一个整数nnn（1≤n≤301 \le n \le 301≤n≤30），表示货币种类数。
接下来nnn行，每行一种货币的名称（不含空格）。
下一行一个整数mmm，表示汇率表的条目数。
接下来mmm行，每行包含：源货币名称、汇率（实数）、目标货币名称。
测试用例之间由一个空行分隔。
输入以n=0n = 0n=0结束。

输出格式

对于每个测试用例，输出一行：

Case case: Yes

或

Case case: No

其中case为测试用例编号（从111开始）。

样例

输入

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 0

输出

Case 1: Yes Case 2: No

题目分析

本题的核心是判断货币兑换图中是否存在乘积大于111的环。由于汇率是乘积关系，而不是加法，需要将乘法转化为加法（取对数），然后使用Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall或Bellman-Ford\texttt{Bellman-Ford}Bellman-Ford算法检测正环。

问题转化

设汇率矩阵R[i][j]R[i][j]R[i][j]表示从货币iii到货币jjj的直接兑换汇率。若存在路径i→k1→k2→⋯→ji \to k_1 \to k_2 \to \dots \to ji→k1→k2→⋯→j，则兑换汇率为R[i][k1]×R[k1][k2]×⋯×R[km][j]R[i][k_1] \times R[k_1][k_2] \times \dots \times R[k_m][j]R[i][k1]×R[k1][k2]×⋯×R[km][j]。套利机会等价于存在一个环i→ii \to ii→i，使得路径乘积>1> 1>1。

对数转化

取自然对数：ln⁡(R[i][j])\ln(R[i][j])ln(R[i][j])。则路径乘积>1> 1>1等价于∑ln⁡(R)>0\sum \ln(R) > 0∑ln(R)>0。问题转化为检测是否存在正权环。

算法选择

由于n≤30n \le 30n≤30，可以使用Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法的变体，直接维护最大路径乘积：
dist[i][j]=max⁡k(dist[i][k]×dist[k][j]) dist[i][j] = \max_{k} (dist[i][k] \times dist[k][j])dist[i][j]=kmax(dist[i][k]×dist[k][j])
初始时，dist[i][i]=1dist[i][i] = 1dist[i][i]=1，有直接汇率的dist[i][j]=dist[i][j] =dist[i][j]=汇率，否则为000（表示不可达）。经过nnn次松弛后，若存在dist[i][i]>1dist[i][i] > 1dist[i][i]>1，则存在套利机会。

实现细节

使用map<string, int>将货币名称映射为整数索引。
初始化距离矩阵为000（不可达），对角线为111。
读入汇率时，将对应位置设为汇率。
执行三重循环更新：若dist[i][k]>0dist[i][k] > 0dist[i][k]>0且dist[k][j]>0dist[k][j] > 0dist[k][j]>0，则dist[i][j]=max⁡(dist[i][j],dist[i][k]×dist[k][j])dist[i][j] = \max(dist[i][j], dist[i][k] \times dist[k][j])dist[i][j]=max(dist[i][j],dist[i][k]×dist[k][j])。
最后检查所有dist[i][i]>1dist[i][i] > 1dist[i][i]>1即可。

复杂度分析

Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall时间复杂度O(n3)O(n^3)O(n3)，n≤30n \le 30n≤30，完全可接受。

代码实现

// Arbitrage (II)// UVa ID: 436// Verdict: Accepted// Submission Date: 2016-07-21// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constdoubleEPSILON=1e-7;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);doublematrix[40][40];intn,m,cases=0;while(cin>>n,n){for(inti=0;i<40;i++)for(intj=0;j<40;j++)matrix[i][j]=-1.0;map<string,int>currency;string currency_name;for(inti=1;i<=n;i++){cin>>currency_name;currency[currency_name]=i;}cin>>m;string start_currency,end_currency;doublerate;for(inti=1;i<=m;i++){cin>>start_currency>>rate>>end_currency;matrix[currency[start_currency]][currency[end_currency]]=rate;}for(intk=1;k<=n;k++)for(inti=1;i<=n;i++)for(intj=1;j<=n;j++){if(matrix[i][k]>0.0&&matrix[k][j]>0.0){if(matrix[i][k]*matrix[k][j]>matrix[i][j]+EPSILON)matrix[i][j]=matrix[i][k]*matrix[k][j];}}boolarbitrage=false;for(inti=1;i<=n;i++)if(matrix[i][i]>1.0+EPSILON){arbitrage=true;gotoskip;}skip:cout<<"Case "<<++cases<<": "<<(arbitrage?"Yes":"No")<<'\n';}return0;}