UVa 104 Arbitrage

解題策略

Some Hints about uVA 104 
gits大大說得很清楚，我就不囉唆作法了。

閒聊

苦思良久的UVa 104終於在 gits 幾乎手把手的帶領下寫出來了，了結了多天以來的心中懸念。XDDD稍微變化題，馬上就把我土法煉鋼學會的Floyd-Warshall 打回原型。連F-W要用二維還是三維陣列來建表都搞不清楚，唉，由這題可以知道我的DP/Graph有待磨練。

只有與問題面對面的對決，在測資跟Bug中打滾一番後，才能對Algorithm有更深刻的體會吧。這也是我寫ACM的目的與樂趣所在。不過...這題還是有點心虛阿.....orz 只能說敗給你了Modified Floyd-Warshall，還未夠班....總有一天我要能秒殺這題。

	/**
	* UVa 104 Arbitrage
	* Author: chchwy
	* Last Modified: 2011/01/30
	* Tag: Dynamic Programming, Floyd-Warshall
	*/
	#include<iostream>
	enum {MAX = 20};
	int main()
	{
	int n; //the dimension of table
	double profit[MAX][MAX][MAX];
	int path[MAX][MAX][MAX]; //backtracking
	while (scanf("%d", &n) == 1)
	{
	memset(profit, 0, sizeof(profit)); // init profit
	//profit[0][i][j] = input for the program
	//profit[0][i][i] = 1, for all i
	//path[0][i][j] = i, for all i, j
	for (int i = 0; i < n; ++i)
	{
	for (int j = 0; j < n; ++j)
	{
	if (i == j)
	profit[0][i][j] = 1.0;
	else
	scanf("%lf", &profit[0][i][j]);
	path[0][i][j] = i;
	}
	}
	//Floyd-Warshall
	for (int steps = 1; steps < n; ++steps)
	{
	for (int k = 0; k < n; ++k) //intermediate node k
	{
	for (int i = 0; i < n; ++i) //path from i to j
	{
	for (int j = 0; j < n; ++j)
	{
	double tmp = profit[steps - 1][i][k] * profit[0][k][j];
	if (tmp > profit[steps][i][j])
	{
	profit[steps][i][j] = tmp;
	path[steps][i][j] = k;
	}
	}
	}
	}
	}
	//Find the shortest path to profit 1%
	int steps, targetNo = -1; //targetNo = the number of currency we want
	for (steps = 1; steps < n; steps++)
	{
	for (int i = 0; i < n; i++)
	{
	if (profit[steps][i][i] > 1.01)
	{
	targetNo = i;
	break;
	}
	}
	if (targetNo != -1)
	break;
	}
	//output
	if (targetNo == -1)
	{
	printf("no arbitrage sequence exists\n");
	}
	else
	{
	int outputSeq[MAX]; //for reverse sequnece
	int index = 0;
	int currentNo = targetNo;
	outputSeq[index++] = targetNo;
	for (int s = steps; s >= 0; --s) //path from targetNo to currentNo
	{
	currentNo = path[s][targetNo][currentNo];
	outputSeq[index++] = currentNo;
	}
	for (int i = index - 1; i > 0; --i)
	printf("%d ", outputSeq[i] + 1);
	printf("%d\n", outputSeq[0] + 1);
	}
	}
	return 0;
	}

view raw 104.cpp hosted with ❤ by GitHub