algorithm - 用图论找到套利

Question

我正在尝试解决这个问题:https://open.kattis.com/problems/arbitrage

If you are going to travel to the World Finals, you cannot rely on Czech Crowns. You would have to exchange your money for various foreign currencies. This problem deals with multiple currencies and their exchange rates. Your task is to verify that some set of exchange rates is safe, namely detect a possibility of so-called arbitrage.

An arbitrage is a risk-free combination of buy and sell operations that gains profit from imbalance in market prices. The prices may apply to various things, typically stock exchange but also currencies.

Input The input consists of several test cases. Each case begins with a line containing one positive integer number 𝐶, 1≤𝐶≤200, the number of currencies.

The second line of each test case contains 𝐶 currency codes separated by a space. Each code is composed of 3 uppercase letters and all codes in one test case are different.

The third line contains one integer number 𝑅,0≤𝑅≤𝐶⋅(𝐶−1), the number of exchange rates available. Each of the following 𝑅 lines contains one exchange rate in the following format: first currency code, space, second currency code, space, integer number 𝐴𝑖, colon (’:’), and integer number 𝐵𝑖. The meaning is as follows: If you pay 𝐴𝑖 units of the first currency, you will get 𝐵𝑖 units of the second currency. You may assume that 1≤𝐴𝑖,𝐵𝑖≤100 and that the two currencies are different.

The last test case is followed by a line with 𝐶=0.

我的方法是在每个节点上做一个 dfs，检查是否存在乘积大于 1 的循环。

这在 O(n^2) 中运行.

有没有更快的解决方案？

Answer 1

澄清一下，这个问题有两个输入大小的度量； C 是货币数量，R 是可用汇率的数量。从每种货币中使用 DFS 的“蛮力”解决方案是 O(C² + CR)，其中通常 R 可以达到 O(C²) 本身。

该问题可以建模为在图中找到负权重循环。节点是货币，边是汇率对，边权重是-log(r)汇率r .使用负对数意味着当且仅当汇率的乘积大于 1 时，周期的权重之和为负。

寻找负权重循环通常是通过采用标准的最短路径算法来实现的，例如 Bellman-Ford在 O(CR) 时间内，或 Floyd-Warshall在 O(C³) 时间内。在 R 为 O(C) 或更大的情况下，这些都不比您的解决方案渐近更好，但可能值得进行基准测试，看看替代方案在实践中是否更快。