POJ 2240 Arbitrage：最短路 Floyd

POJ 2240 Arbitrage：最短路 Floyd2015-02-25Arbitrage：http://poj.org/problem？id=2240

大意：

给你m种货币，给你m种货币兑换规则，问通过这些规则最后能不能盈利。eg：1美元换0.5英镑，1英镑换10法郎，1法郎换0.21美元，这样1美元能换0.5*10*0.21=1.05美元，净赚0.05美元。

思路：

用Floyd找出每两种钱之间的最大兑换关系，遍历一遍，看有没有那种钱币最后能盈利，有就输出Yes，没有就是No。在处理钱币名称与编号之间的关系时，可以用map存（比较好用），当然也可以用字符串比较。

#include <stdio.h>#include <iostream>#include <map>#define INF 0x3f3f3f3fusing namespace std;char money[30];char change1[30], change2[30];double trans;double Map[50][50];int n, m;///用map建立字符串与编号之间的关系map<string, int>p;void Floyd（）{for（int k = 1; k <= n; k++）{for（int i = 1; i <= n; i++）{for（int j = 1; j <= n; j++）{///变形的最大路径把‘+’变为了‘*’if（Map[i][j] < Map[i][k]*Map[k][j]）{Map[i][j] = Map[i][k]*Map[k][j];}}}}return ;}void Solve（）{int cnt = 1;while（~scanf（"%d%*c", &n） && n）{for（int i = 1; i <= n; i++）{scanf（"%s", money）;p[money] = i;Map[i][i] = 1;}scanf（"%d%*c", &m）;for（int i = 1; i <= m; i++）{scanf（"%s%lf%s", change1, &trans, change2）;Map[p[change1]][p[change2]] = trans; ///去map中的数据建图}Floyd（）;bool flag = false;for（int i = 1; i <= n; i++）{if（Map[i][i] > 1）{flag = true;break;}}if（flag）{printf（"Case %d: Yes
", cnt++）;}else{printf（"Case %d: No
", cnt++）;}}}int main（）{Solve（）;return 0;}

From：cnblogs GLsilence