[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)，代码如下：

	//POJ 2240
	/*
	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.
	Input
	The input 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.
	Output
	For each test case, print one line telling whether arbitrage is possible or not in the format "Case case: Yes" respectively "Case case: No".
	*/
	#include <iostream>
	#include <cstring>
	#include <map>
	#include <cstdio>
	using namespace std;
	const int MAXN = 35;
	const int MAXM = 1000;
	double dist[MAXN];
	int N, M;
	map<string, int> id;
	struct Edge
	{
	int from, to;
	double weight;
	} edges[MAXM];
	bool hasIncreasingCycle()
	{
	//run bellman ford to find increasing cycle
	//Exchanges which do not appear in the table are impossible
	//which means the graph is strongly connected, so we can run
	//total N times and find if dist[1] is larger than 1, and that
	//is enough
	//of course, if we run N - 1 times first and find if there is
	//dist[i] increases in Nth run, it also works
	for(int i = 0; i < MAXN; ++i)dist[i] = 0;
	dist[1] = 1.0;
	for(int i = 0; i < N; ++i)
	{
	for(int j = 0; j < M; ++j)
	{
	int from = edges[j].from, to = edges[j].to;
	double rate = edges[j].weight;
	if(dist[from] * rate > dist[to])dist[to] = dist[from] * rate;
	}
	}
	return dist[1] > 1.0;
	}
	int main()
	{
	int count = 0;
	while(scanf("%d", &N) != EOF)
	{
	if(N == 0) break;
	id.clear();
	string s;
	for(int i = 1; i <= N; i++)
	{
	cin >> s;
	id[s] = i;
	}
	scanf("%d", &M);
	string s1,s2;
	double rate;
	for(int i = 0; i < M; i++)
	{
	cin >> s1 >> rate >> s2;
	edges[i].from = id[s1];
	edges[i].to = id[s2];
	edges[i].weight = rate;
	}
	printf("Case %d: ", ++count);
	if(hasIncreasingCycle())printf("Yes\n");
	else printf("No\n");
	}
	return 0;
	}

view raw POJ_2240_ Arbitrage_Bellman_Ford.cpp hosted with ❤ by GitHub

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

	//POJ 2240
	/*
	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.
	Input
	The input 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.
	Output
	For each test case, print one line telling whether arbitrage is possible or not in the format "Case case: Yes" respectively "Case case: No".
	*/
	#include <iostream>
	#include <cstring>
	#include <map>
	#include <cstdio>
	using namespace std;
	const int MAXN = 35;
	const int MAXM = 1000;
	double dist[MAXN][MAXN];
	int N, M;
	map<string, int> id;
	struct Edge
	{
	int from, to;
	double weight;
	} edges[MAXM];
	bool hasIncreasingCycle()
	{
	//run floyd to detect increasing cycle
	for(int k = 1; k <= N; ++k)
	for(int i = 1; i <= N; ++i)
	for(int j = 1; j <= N; ++j)
	dist[i][j] = max(dist[i][j], dist[i][k] * dist[k][j]);
	for(int i = 1; i <= N; ++i)
	if(dist[i][i] > 1.0)return true;
	return false;
	}
	int main()
	{
	int count = 0;
	while(scanf("%d", &N) != EOF)
	{
	if(N == 0) break;
	id.clear();
	string s;
	memset(dist, 0, sizeof(dist));
	for(int i = 1; i <= N; i++)
	{
	cin >> s;
	id[s] = i;
	dist[i][i] = 1.0;
	}
	scanf("%d", &M);
	string s1,s2;
	double rate;
	for(int i = 0; i < M; i++)
	{
	cin >> s1 >> rate >> s2;
	dist[id[s1]][id[s2]] = rate;
	}
	printf("Case %d: ", ++count);
	if(hasIncreasingCycle())printf("Yes\n");
	else printf("No\n");
	}
	return 0;
	}

view raw POJ_2240_ Arbitrage_Floyd.cpp hosted with ❤ by GitHub