题意简述

有 N 次挤奶，在 M 天 内完成，需要求出每次挤奶的最早可行日期，同时满足两个硬性约束：

基础约束：第 i 次挤奶的日期 不能早于第 Sᵢ 天；
时序约束：给定 C 条规则 (a, b, x)，要求第 b 次挤奶的日期 ≥ 第 a 次挤奶的日期 + x（b 比 a 至少晚 x 天）；
题目保证所有约束无矛盾，一定存在合法方案。

题目思路

步骤 1：建图

我们引入超级源点 0，这样可以让 SPFA 能一次性处理所有规则，不用额外写代码特殊处理。

值得注意的是，超级源点 0 到其他点的单向边代价应该是这个点不早于第 Sᵢ 天挤奶的时间，也就是 Sᵢ ，不然的话SPFA不会按照限定的时间，可能会提前。

步骤 2：SPFA 初始化

距离数组 dis[]：全部初始化为负无穷（因为我们要求的是最长路）
超级源点 dis[0] = 0
用队列存储待松弛的节点，初始把节点 0 入队
标记数组 vis[]：标记节点是否在队列中，避免重复入队

步骤 3：SPFA 最长路松弛

标准 SPFA 流程，但是判断 dis[v] > dis[u] + w 改成 dis[v] < dis[u] + w

步骤 4：得到答案

队列空时，dis[i] 就是第 i 个变量的最小合法值（满足所有约束）。

然后直接输出就可以了，恭喜你做完了这道题！

AC代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 5, INF = 1e9 + 7;
int n, m, kk;        // n:挤奶次数 m:总天数 kk:约束条数
int lim[N];          // 存储每次挤奶的最早天数下限
vector<vector<pair<int, int>>> e(N); // 邻接表存图
bool vis[N];         // SPFA标记数组
ll dis[N];           // 存储答案（最长路结果）

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> kk;
	for (int i = 1; i <= n; ++i) cin >> lim[i]; // 读取下限约束
	for (int i = 1; i <= kk; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		e[u].emplace_back(v, w); // 建约束边：v >= u + w
	}
	for (int i = 1; i <= n; ++i) {
		e[0].emplace_back(i, lim[i]); // 超级源点：满足i >= lim[i]
	}
	fill(dis + 1, dis + n + 1, -INF); // 最长路初始化：负无穷
	vis[0] = true;
	dis[0] = 0;
	queue<int> q;
	q.emplace(0);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		vis[u] = false;
		for (auto tmp : e[u]) {
			int v, w;
			tie(v, w) = tmp;
			if (dis[v] < dis[u] + w) { // 最长路松弛操作
				dis[v] = dis[u] + w;
				if (!vis[v]) {
					vis[v] = true;
					q.emplace(v);
				}
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		cout << dis[i] << "\n"; // 输出每次挤奶的最早日期
	}
	return 0;
}

P6145 [USACO20FEB] Timeline G SPFA差分约束最长路题解