在有向图上同时传播路径最低买价和最大已获利润。
OJ: luogu
题目 ID: P1073
难度:提高
标签:图上 DP最短路队列松弛python
日期: 2026-07-17 03:00
题意
沿 1 到 n 的可重复有向路线，最多买卖一次，求最大利润。
思路
每个节点维护到达它的路径最低价格 minimum 和最大已获利润 profit。沿边传播时，新最低价取较小值，新利润取旧利润与“当前城市售价减此前最低价”的较大值；任一状态改善就重新入队，直到收敛。
Python 知识
- 两个单调状态数组共同描述到达节点后的最优信息。
bytearray保存是否在队列，避免重复入队。- 双向道路按输入类型补反向边。
代码
python
import sys
from collections import deque
input = sys.stdin.buffer.readline
n, roads = map(int, input().split())
price = [0] + list(map(int, input().split()))
graph = [[] for _ in range(n + 1)]
for _ in range(roads):
x, y, kind = map(int, input().split())
graph[x].append(y)
if kind == 2:
graph[y].append(x)
infinity = 10**9
minimum = [infinity] * (n + 1)
profit = [-1] * (n + 1)
in_queue = bytearray(n + 1)
minimum[1] = price[1]
profit[1] = 0
queue = deque([1])
in_queue[1] = 1
while queue:
node = queue.popleft()
in_queue[node] = 0
for neighbor in graph[node]:
next_minimum = min(minimum[node], price[neighbor])
next_profit = max(profit[node], price[neighbor] - minimum[node])
if next_minimum < minimum[neighbor] or next_profit > profit[neighbor]:
minimum[neighbor] = min(minimum[neighbor], next_minimum)
profit[neighbor] = max(profit[neighbor], next_profit)
if not in_queue[neighbor]:
queue.append(neighbor)
in_queue[neighbor] = 1
print(profit[n])原有 C++ 版本仍保留：
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXE = 1000005;
const int INF = 1000000000;
int n, m;
int price_city[MAXN];
int head[MAXN], to[MAXE], nxt[MAXE], edge_cnt;
int rev_head[MAXN], rev_to[MAXE], rev_nxt[MAXE], rev_edge_cnt;
int min_buy[MAXN]; // min_buy[x] 表示从 1 到 x 的某条路线上能遇到的最低价格。
int max_sell[MAXN]; // max_sell[x] 表示从 x 到 n 的某条路线上能遇到的最高价格。
bool in_queue[MAXN];
void add_edge(int u, int v) {
edge_cnt++;
to[edge_cnt] = v;
nxt[edge_cnt] = head[u];
head[u] = edge_cnt;
rev_edge_cnt++;
rev_to[rev_edge_cnt] = u;
rev_nxt[rev_edge_cnt] = rev_head[v];
rev_head[v] = rev_edge_cnt;
}
void read_input() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> price_city[i];
}
for (int i = 1; i <= m; i++) {
int x, y, z;
cin >> x >> y >> z;
add_edge(x, y);
if (z == 2) {
add_edge(y, x);
}
}
}
void calc_min_buy() {
for (int i = 1; i <= n; i++) {
min_buy[i] = INF;
in_queue[i] = false;
}
queue<int> que;
min_buy[1] = price_city[1];
que.push(1);
in_queue[1] = true;
while (!que.empty()) {
int u = que.front();
que.pop();
in_queue[u] = false;
for (int i = head[u]; i != 0; i = nxt[i]) {
int v = to[i];
int value = min(min_buy[u], price_city[v]);
if (value < min_buy[v]) {
min_buy[v] = value;
if (!in_queue[v]) {
que.push(v);
in_queue[v] = true;
}
}
}
}
}
void calc_max_sell() {
for (int i = 1; i <= n; i++) {
max_sell[i] = -INF;
in_queue[i] = false;
}
queue<int> que;
max_sell[n] = price_city[n];
que.push(n);
in_queue[n] = true;
while (!que.empty()) {
int u = que.front();
que.pop();
in_queue[u] = false;
for (int i = rev_head[u]; i != 0; i = rev_nxt[i]) {
int v = rev_to[i];
int value = max(max_sell[u], price_city[v]);
if (value > max_sell[v]) {
max_sell[v] = value;
if (!in_queue[v]) {
que.push(v);
in_queue[v] = true;
}
}
}
}
}
void solve() {
calc_min_buy();
calc_max_sell();
int answer = 0;
for (int i = 1; i <= n; i++) {
if (min_buy[i] == INF || max_sell[i] == -INF) {
continue;
}
answer = max(answer, max_sell[i] - min_buy[i]);
}
cout << answer << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
solve();
return 0;
}复杂度
队列松弛最坏较高，价格仅到 100 时状态下降次数有限；空间 O(n+m)。
总结
“先买后卖”沿路径只需记最低历史价格和最大历史差值。
