【floyd神器】HDU 1217 Arbitrage
http://acm.hdu.edu.cn/showproblem.php?pid=1217题意：给出各种钱之间的兑换机制，求不断兑换后是否可以产生利润？
对于第一个案例：start with 1 US dollar and buy 0.5 * 10.0 * 0.21 = 1.05 US dollars, making a profit of 5 percent
Sample Input
3
USDollar
BritishPound
FrenchFranc
3
USDollar 0.5 BritishPound
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar
3
USDollar
BritishPound
FrenchFranc
6
USDollar 0.5 BritishPound
USDollar 4.9 FrenchFranc
BritishPound 10.0 FrenchFranc
BritishPound 1.99 USDollar
FrenchFranc 0.09 BritishPound
FrenchFranc 0.19 USDollar
0
Sample Output
Case 1: Yes
Case 2: No
#include <iostream>#include <fstream>#include <algorithm>#include <string>#include <set>#include <map>#include <queue>#include <utility>#include <stack>#include <list>#include <vector>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>//#include <ctime>#include <ctype.h>using namespace std;#define L long long#define inf 0x3fffffff#define M 1005map<string, int> m; //映射double mon;int main(){double x;int n, i, k, j, cc = 1;string s, p;while (cin >> n, n){for (i = 0; i < n; i++){cin >> s;m = i; //把string映射为的编号}cin >> k;memset (mon, 0, sizeof(mon)); //初始化while (k--){cin >> s >> x >> p;mon]] = x; //从s号变为p号要乘以x} /*****************floyd神器*****************/for (i = 0; i < n; i++)for (j = 0; j < n; j++)for (k = 0; k < n; k++) //floyd-构造所有情况的神器if (mon < mon * mon) //就像路径，从j到k可以由j到i再到kmon = mon * mon; //更新，所谓的松弛技术 /*****************floyd神器*****************/for (i = 0; i < n; i++)if (mon > 1.0) //经过变换后>1.0说明获得利润break;printf ("Case %d: ", cc++);if (i < n)puts ("Yes");else puts ("No");}return 0;}
页:
[1]