[POJ]2240 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. 

给定一组币种之间的汇率，我们要求是否有套汇的可能。我们根据要求建图，这道题就是要我们求图中是否存在环，我们沿着环走可以使得我们的钱增加。这里边之间的关系是相乘，并且求的是最长路径，和Dijksra不同，Bellman-Ford和Floyd的做法可以应用在最长路径上，具体可以参考这篇文章。
对于Bellman Ford，鉴于我们从某一点v出发，最多经过N条边就可以回到v，如果我们初始有1块钱并且图中存在可以套汇的环的话，我们对所有边进行N次relax肯定会发现回到v点之后会多于一块钱。我们按照这个思路即可发现是否存在套汇环，时间复杂度O(V * E)，代码如下：


Floyd的方法更直接了，所有dist[i][i]初始化为1，我们跑完直接查看任意dist[i][i]是否大于1即可。时间复杂度O(V^3)，代码如下：