把记忆约束建成带权 DAG，在拓扑序上做最长路转移，`dp[i]` 表示第 i 次挤奶能安排的最早日期。
OJ: luogu
题目 ID: P6145
难度:普及/提高-
标签:图论拓扑排序dag动态规划
日期: 2026-06-19 23:19
题意
有 n 次挤奶，第 i 次挤奶最早不能早于 S[i] 这一天。
另外有若干条记忆 (a, b, x)，表示第 b 次挤奶至少要在第 a 次挤奶之后 x 天进行，也就是：
day[b] >= day[a] + x
题目保证这些记忆没有矛盾。要求输出每一次挤奶在满足所有条件时的最早日期。
样例图
这张图把样例中的下界和依赖关系画出来：
digraph G {
rankdir=LR;
1 [label="1\nS=1"];
2 [label="2\nS=2"];
3 [label="3\nS=3"];
4 [label="4\nS=4"];
1 -> 2 [label="+5"];
2 -> 4 [label="+2"];
3 -> 4 [label="+4"];
}
例如点 2 本来下界是 2，但因为 2 >= 1 + 5，所以它至少要到第 6 天。
点 4 既要满足 4 >= 2 + 2，又要满足 4 >= 3 + 4，所以要取这些限制中的最大值，最后得到 8。
思路
先看一个小数据暴力：
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 15;
int n, m, c;
int start_day[MAXN];
struct Edge {
int from, w;
};
vector<Edge> pre[MAXN]; // pre[i] : 所有指向 i 的前驱边
// 暴力枚举所有能影响 u 的前驱链，返回 u 的最早可行日期。
int dfs(int u) {
int best = start_day[u];
for (Edge e : pre[u]) {
best = max(best, dfs(e.from) + e.w);
}
return best;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> c;
for (int i = 1; i <= n; i++) {
cin >> start_day[i];
pre[i].clear();
}
for (int i = 1; i <= c; i++) {
int u, v, w;
cin >> u >> v >> w;
pre[v].push_back({u, w});
}
for (int i = 1; i <= n; i++) {
cout << dfs(i) << '\n';
}
return 0;
}这个暴力直接递归枚举某个点所有可能影响它的前驱链。
如果定义 f(i) 表示第 i 次挤奶能安排的最早日期，那么：
- 至少要满足自己的下界：
f(i) >= S[i] - 对每条约束
u -> i (w)，还要满足f(i) >= f(u) + w
因此就有转移：
f(i) = max(S[i], f(u1) + w1, f(u2) + w2, ...)
这正是一个 DAG 上的最长路模型，只不过：
- 点的初值是
S[i] - 边权是约束里的
x
直接递归会反复计算很多重叠子问题，所以正式做法改成拓扑排序 + DP。
做法：
-
把每次挤奶看成一个点。
-
对每条记忆
(a, b, x)建边a -> b，边权为x。 -
初始令
dp[i] = S[i]。 -
求拓扑序。
-
按拓扑序枚举点
u，对每条边u -> v (w)做：dp[v] = max(dp[v], dp[u] + w) -
最后每个
dp[i]就是答案。
代码结构和你算法书里的拓扑模板一致：add_edge() 建图，kahn() 求序，然后在线性顺序上做带权转移。
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n, m, c;
int start_day[MAXN]; // start_day[i] : 第 i 次挤奶最早不能早于哪一天
int dp[MAXN]; // dp[i] : 第 i 次挤奶在满足条件下的最早日期
struct Edge {
int to, w;
};
struct TopologicalSort {
int n;
vector<vector<Edge>> graph;
vector<int> indeg;
explicit TopologicalSort(int n = 0) {
init(n);
}
void init(int _n) {
n = _n;
graph.assign(n + 1, vector<Edge>());
indeg.assign(n + 1, 0);
}
void add_edge(int u, int v, int w) {
graph[u].push_back({v, w});
indeg[v]++;
}
vector<int> kahn() {
queue<int> q;
vector<int> deg = indeg;
vector<int> order;
for (int i = 1; i <= n; i++) {
if (deg[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);
for (Edge e : graph[u]) {
int v = e.to;
deg[v]--;
if (deg[v] == 0) {
q.push(v);
}
}
}
return order;
}
};
TopologicalSort topo;
void read_input() {
cin >> n >> m >> c;
topo.init(n);
for (int i = 1; i <= n; i++) {
cin >> start_day[i];
dp[i] = start_day[i];
}
for (int i = 1; i <= c; i++) {
int u, v, w;
cin >> u >> v >> w;
topo.add_edge(u, v, w);
}
}
void solve() {
vector<int> order = topo.kahn();
for (int u : order) {
for (Edge e : topo.graph[u]) {
int v = e.to;
dp[v] = max(dp[v], dp[u] + e.w);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
solve();
for (int i = 1; i <= n; i++) {
cout << dp[i] << '\n';
}
return 0;
}复杂度
设点数为 n，约束条数为 c。
- 拓扑排序：
- DP 转移：
总时间复杂度
总结
这题表面上像“推时间线”，实质上就是带初始下界的 DAG 最长路。看见 day[v] >= day[u] + x 这种形式，就要想到用拓扑序把所有限制一层层往后推。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
