题目链接
题意：给定一些国家货币的汇率，问能否通过不断换货币使钱得到增长
思路：floyd，完事后判断一下有没有连到自己能大于1的情况
代码：
#include #include #include #include #include using namespace std; const int N = 35; int n; double g[N][N]; map hash; int main() { int cas = 0; while (~scanf("%d", &n) && n) { string a, b; hash.clear(); for (int i = 1; i <= n; i++) { cin >> a; hash[a] = i; } int m; double f; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) g[i][j] = 1.0; else g[i][j] = 0; } } scanf("%d", &m); while (m--) { cin >> a >> f >> b; int u = hash[a], v = hash[b]; g[u][v] = f; } for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) g[i][j] = max(g[i][j], g[i][k] * g[k][j]); } } printf("Case %d: ", ++cas); int flag = 1; for (int i = 1; i <= n; i++) { if (g[i][i] > 1.0) { printf("Yes\n"); flag = 0; break; } } if (flag) printf("No\n"); } return 0; }