本文共 2851 字，大约阅读时间需要 9 分钟。
在这个问题中，我们需要找到一条路径，使得沿着路径购买和出售水晶球的差价最大化。路径中的点可以重复出现，这意味着我们需要考虑环路的可能性。
为了解决这个问题，我们可以将其分解为两个部分：
最后，我们遍历从2号点到n-1号点的所有点，计算每个点的销售收入减去购买成本的差值，找出最大的差值作为结果。
建立邻接表：
a1和a2分别表示图的边。a1用于计算最小购买成本，a2用于计算最大销售收入。add1和add2函数用于添加边到邻接表中。SPFA算法实现：
spfa1(int o)：从起点o出发，计算最小购买成本数组minn。spfa2(int o)：从终点o出发，计算最大销售收入数组maxn。计算结果：
minn数组为大值，使用spfa1计算最小购买成本。maxn数组为起点值，使用spfa2计算最大销售收入。maxn[i] - minn[i]。#include#include using namespace std;#define N 1000005#define M 5000005struct stu { int to; int next; int w;};stu a1[M], a2[M];int head1[M], head2[M];int b[M], c[N];int w[N];int minn[N], maxn[N];int tot1, tot2, head, tail;void add1(int x, int y) { tot1++; a1[tot1].to = y; a1[tot1].next = head1[x]; head1[x] = tot1;}void add2(int x, int y) { tot2++; a2[tot2].to = y; a2[tot2].next = head2[x]; head2[x] = tot2;}void spfa1(int o) { minn[o] = w[o]; head = 0; tail = 1; b[1] = o; c[o] = 1; do { head = (head % N) + 1; int k = b[head]; for (int i = head1[k]; i < M; i++) { if (minn[a1[i].to] > min(minn[k], w[a1[i].to])) { minn[a1[i].to] = min(minn[k], w[a1[i].to]); if (c[a1[i].to] == 0) { tail++; b[tail] = a1[i].to; c[a1[i].to] = 1; } } } c[k] = 0; } while (head < tail);}void spfa2(int o) { maxn[o] = w[o]; head = 0; tail = 1; b[1] = o; c[o] = 1; do { head = (head % N) + 1; int k = b[head]; for (int i = head2[k]; i < M; i++) { if (maxn[a2[i].to] < max(maxn[k], w[a2[i].to])) { maxn[a2[i].to] = max(maxn[k], w[a2[i].to]); if (c[a2[i].to] == 0) { tail++; b[tail] = a2[i].to; c[a2[i].to] = 1; } } } c[k] = 0; } while (head < tail);}int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> w[i]; minn[i] = 2147483647; } for (int i = 1; i <= m; i++) { int x, y, z; cin >> x >> y >> z; add1(x, y); add2(y, x); if (z == 2) { add1(y, x); add2(x, y); } } spfa1(1); for (int i = 1; i <= n; i++) { c[i] = 0; } spfa2(n); int m_max = 0; for (int i = 2; i <= n - 1; i++) { m_max = max(m_max, maxn[i] - minn[i]); } cout << m_max << endl;}
a1和a2，分别用于计算最小购买成本和最大销售收入。通过这种方法，我们能够高效地解决最优贸易问题，找到最大的利润路径。
转载地址：http://tqpzz.baihongyu.com/