【floyd神器】HDU 1217 Arbitrage

基德KID.1412

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[35][35];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映射为[0,n-1]的编号}cin >> k;memset (mon, 0, sizeof(mon));   //初始化while (k--){cin >> s >> x >> p;mon[m][m[p]] = 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[j][k] < mon[j] * mon[k])                      //就像路径，从j到k可以由j到i再到kmon[j][k] = mon[j] * mon[k]; //更新，所谓的松弛技术        /*****************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;}