题目描述：
有n种货币，给出它们之间的汇率，并且汇率是可以传递的，即如果1单位A货币可以兑换m单位B货币，1单位B货币可以兑换p单位C货币，那么1单位A货币就可以兑换m*p单位C货币。现在某人持有1单位A货币，他想通过一系列的兑换，使得他的钱最多，问最多能有多少。
输入：
第一行两个整数n和m，n表示货币的种类数，m表示汇率表的条数。接下来m行，每行三个数x，y，z，表示1单位的x货币可以兑换z单位的y货币。
输出：
输出一个数，表示最多能兑换多少单位的货币，保留三位小数。
样例输入：
3 3
1 2 0.2
2 3 0.5
3 1 10
样例输出：
11.110
题目分析：
本题是一个经典的货币兑换问题，可以通过图论中的Bellman-Ford算法来解决。我们将每种货币看作图中的一个节点，汇率看作边，边的权重为汇率的对数。这样，问题就转化为在图中寻找从起点（A货币）到其他节点的最长路径。
具体步骤如下：
- 构建图：将n种货币作为节点，m个汇率作为边，边的权重为汇率的对数。
- 使用Bellman-Ford算法计算从起点（A货币）到其他节点的最长路径。
- 输出最长路径的长度，即最多能兑换的货币单位数。
代码实现：
#include
const int MAXN = 1010; const double INF = 1e9;
struct Edge { int from, to; double rate; };
int n, m;
vector
void bellman_ford(int start) { fill(dist, dist + n + 1, -INF); dist[start] = 1;
for (int i = 1; i <= n; ++i) {
for (auto &edge : edges) {
int from = edge.from;
int to = edge.to;
double rate = edge.rate;
if (dist[from] > 0 && dist[to] < dist[from] * rate) {
dist[to] = dist[from] * rate;
}
}
}}
int main() { cin >> n >> m; int x, y; double z; for (int i = 0; i < m; ++i) { cin >> x >> y >> z; edges.push_back({x, y, z}); }
bellman_ford(1);
double max_currency = 0;
for (int i = 1; i <= n; ++i) {
max_currency = max(max_currency, dist[i]);
}
printf("%.3f\n", max_currency);
return 0;}
代码解释：
- 定义结构体Edge来存储边的相关信息，包括起点、终点和汇率。
- 使用bellman_ford函数来实现Bellman-Ford算法，计算从起点到其他节点的最长路径。
- 在主函数中，读取输入数据，构建图，并调用bellman_ford函数计算最多能兑换的货币单位数。
- 输出结果，保留三位小数。
注意：
- 在Bellman-Ford算法中，我们初始化起点到自身的距离为1，其他节点的距离为负无穷。
- 在更新距离时，我们只考虑从有正距离的节点出发的边。
- 最后输出的是所有节点中距离最大的值，即最多能兑换的货币单位数。
通过以上步骤，我们可以有效地解决这个货币兑换问题。
发表回复