思路是将可以换得的不同种的货币的数量当作节点，每个兑换点当成边，然后我抄了个算法导论里面的Bellman-Ford算法，一次就过了。看discussion里面很多讨论精度的，我想都没想过……
#include <iostream> using namespace std; struct Point{ int a, b; double Rab, Cab, Rba, Cba; }; int main() { int n, m, s; double money; Point point[101]; cin >> n >> m >> s >> money; for (int i = 0; i < m; i++){ cin >> point[i].a >> point[i].b >> point[i].Rab >> point[i].Cab >> point[i].Rba >> point[i].Cba; } double node[101]; memset(node, 0, sizeof(node)); node[s] = money; for (int j = 1; j <= n - 1; j++){ for (int i = 0; i < m; i++){ if (node[point[i].a] < (node[point[i].b] - point[i].Cba) * point[i].Rba) node[point[i].a] = (node[point[i].b] - point[i].Cba) * point[i].Rba; if (node[point[i].b] < (node[point[i].a] - point[i].Cab) * point[i].Rab) node[point[i].b] = (node[point[i].a] - point[i].Cab) * point[i].Rab; } } bool flag = true; for (int i = 0; i < m; i++){ if (node[point[i].a] < (node[point[i].b] - point[i].Cba) * point[i].Rba || node[point[i].b] < (node[point[i].a] - point[i].Cab) * point[i].Rab){ flag = false; break; } } cout << (flag ? "NO" : "YES") << endl; return 0; }
原文：http://www.cnblogs.com/caiminfeng/p/4872124.html