「CH6101」最优贸易
传送门
考虑一种贪心的思想：我们要尽量买价格小的货物，并尽量高价转卖。
我们记 :
- \(mn[i]\) 为从点 \(1\) 走到点 \(i\) 经过的价格最小的货物的价格。
- \(mx[i]\) 为从点 \(i\) 走到点 \(n\) 经过的价格最大的货物的价格。
这两个东西可以跑两次 \(\text{SPFA}\) 求得。
那么对于任何一个点，如果它位于最优解对应的路径上，那么该最优值一定不会小于 \(mx[i] - mn[i]\)
那么我们就可以把每个点 \(i\) 的 \(mx[i] - mn[i]\) 取最大值，就一定可以取到最优答案。
参考代码：
#include <cstring>
#include <cstdio>
#include <queue>
#define rg register
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
using namespace std;
template < class T > inline void read(T& s) {
s = 0; int f = 0; char c = getchar();
while ('0' > c || c > '9') f |= c == '-', c = getchar();
while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();
s = f ? -s : s;
}
const int _ = 1e5 + 5, __ = 5e5 + 5;
int tot, head1[_], head2[_], nxt[__ << 2], ver[__ << 2];
inline void Add_edge(int* head, int u, int v)
{ nxt[++tot] = head[u], head[u] = tot, ver[tot] = v; }
int n, m, val[_], mn[_], mx[_], exi[_];
inline void spfa1() {
static queue < int > Q;
while (!Q.empty()) Q.pop();
memset(exi + 1, 0, sizeof (int) * n);
memset(mn + 1, 0x3f, sizeof (int) * n);
Q.push(1), mn[1] = val[1], exi[1] = 1;
while (!Q.empty()) {
int u = Q.front(); Q.pop(), exi[u] = 0;
for (rg int i = head1[u]; i; i = nxt[i]) {
int v = ver[i];
if (mn[v] > min(mn[u], val[v])) {
mn[v] = min(mn[u], val[v]);
if (!exi[v]) exi[v] = 1, Q.push(v);
}
}
}
}
inline void spfa2() {
static queue < int > Q;
while (!Q.empty()) Q.pop();
memset(exi + 1, 0, sizeof (int) * n);
memset(mx + 1, 0, sizeof (int) * n);
Q.push(n), mx[n] = val[n], exi[n] = 1;
while (!Q.empty()) {
int u = Q.front(); Q.pop(), exi[u] = 0;
for (rg int i = head2[u]; i; i = nxt[i]) {
int v = ver[i];
if (mx[v] < max(mx[u], val[v])) {
mx[v] = max(mx[u], val[v]);
if (!exi[v]) exi[v] = 1, Q.push(v);
}
}
}
}
int main() {
#ifndef ONLINE_JUDGE
file("cpp");
#endif
read(n), read(m);
for (rg int i = 1; i <= n; ++i) read(val[i]);
for (rg int u, v, x; m--; ) {
read(u), read(v), read(x);
Add_edge(head1, u, v), Add_edge(head2, v, u);
if (x == 2) Add_edge(head1, v, u), Add_edge(head2, u, v);
}
spfa1(), spfa2();
int ans = 0;
for (rg int i = 1; i <= n; ++i) ans = max(ans, mx[i] - mn[i]);
printf("%d\n", ans);
return 0;
}