POJ 2240 Arbitrage

題意：
    所謂"套匯"指的是透過不斷兌換成別的貨幣，最後再換成原本的貨幣會比本來的錢多。
想法：
    用R[i][j]表示i換成j的匯率，且初始化R[i][i]=1，做Floyd演算法後，去判斷R[i][i]是否大於1，如果大於1表示可以套匯。

	#include <cstdio>
	#include <string>
	#include <map>
	#include <queue>
	using namespace std;
	int main()
	{
	int N, M, Case = 1;
	while (scanf("%d", &N) && N) {
	map<string, int> Map;
	double R[35][35] = {0}; // Rate
	// Initial
	for (int i = 0; i < N; ++i)
	R[i][i] = 1;
	// Input
	char a[100], b[100];
	double rate;
	for (int i = 0; i < N; ++i) {
	scanf("%s", a);
	Map[a] = i;
	}
	scanf("%d", &M);
	for (int i = 0; i < M; ++i) {
	scanf("%s %lf %s", a, &rate, b);
	R[Map[a]][Map[b]] = rate;
	}
	// Floyd
	for (int k = 0; k < N; ++k)
	for (int i = 0; i < N; ++i)
	for (int j = 0; j < N; ++j)
	if (R[i][k]*R[k][j] > R[i][j])
	R[i][j] = R[i][k]*R[k][j];
	// Analysis & Output
	bool Yes = false;
	for (int i = 0; i < N; ++i)
	if (R[i][i] > 1)
	Yes = true;
	printf("Case %d: ", Case++);
	if (Yes) puts("Yes");
	else puts("No");
	}
	}

view raw [POJ] 2240 Arbitrage.cpp hosted with ❤ by GitHub