核心逻辑与数学原理
差分约束系统（System of Difference Constraints）是一种特殊的线性规划形式，包含 $N$ 个变量和 $M$ 个不等式约束。每个不等式的形式均为 $x_i - x_j \le c_k$，其中 $c_k$ 为常数。
该系统的核心在于代数不等式与图论中最短路/最长路三角形不等式的同构性。
1. 最短路拓扑映射
图论中最短路的控制方程为 $dist[v] \le dist[u] + w(u, v)$，移项变形为：
$$dist[v] - dist[u] \le w(u, v)$$
这与差分约束标准型 $x_i - x_j \le c_k$ 在数学结构上完全一致。因此，我们可以将代数问题转化为有向图 $G=(V, E)$：
- 每个变量 $x_i$ 映射为图中的一个顶点 $V_i$。
- 每个约束 $x_i - x_j \le c_k$ 转化为 $x_i \le x_j + c_k$，映射为一条从节点 $j$ 指向节点 $i$ 的有向边 $e(j, i)$，权值为 $c_k$。
2. 负环与无解判定
代数系统可能存在相互矛盾的约束（例如 $x_1 - x_2 \le 2$ 且 $x_2 - x_1 \le -5$，联立得 $0 \le -3$，显然无解）。在有向图中，这种代数矛盾严格对应于负权回路（负环）。如果图中存在一个总权值为负的环路，松弛操作将无限循环，导致 $dist$ 逼近 $-\infty$。此时，差分约束系统无解。由于 Dijkstra 算法无法识别负权和负环，此处的算法引擎必须选择 SPFA。
算法推导与状态设计
根据题意对未知量的取值约束（求最大值或最小值），建图方案遵循两套对偶逻辑：
1. 求最大值（强标定：最短路）
若题目要求在满足所有不等式的前提下，求 $x_i - x_j$ 的最大值，必须将所有条件转化为标准型 $x_A \le x_B + c$。
- 状态推导：由于 $x_i \le x_j + c_1$ 且 $x_i \le x_k + c_2$，要满足所有上界约束，$x_i$ 最终必须受限于所有路径组合中的最小值。也就是说，从全局来看，$x_i - x_j \le \text{dist}(j, i)$。
- 结论：求最大值时使用最短路算法。
2. 求最小值（强标定：最长路）
若题目条件给出的是 $x_i - x_j \ge c_k$，或要求满足条件下的最小值。
- 状态推导：将所有不等式转化为标准下界形式：$x_i \ge x_j + c_k$。
- 最长路三角形不等式：$dist[v] \ge dist[u] + w(u, v) \implies dist[v] - dist[u] \ge w(u, v)$。
- 结论：求最小值时使用最长路算法（将初始化 $dist$ 置为 $-\infty$，松弛条件改为
if (dist[u] + w > dist[v])）。此时，无解的代数特征对应图中的正权回路（正环）。
3. 超级源点建图状态
若图可能不连通，为了保证从源点出发能遍历所有变量，需要引入虚拟超级源点 $x_0$。若题目限制所有变量均为正数（$x_i \ge 1$）或非负数（$x_i \ge 0$），则对所有 $i \in [1, N]$，建立从 $0$ 到 $i$ 的有向边。边权取决于约束方向（最短路连 $0$ 权边，最长路连 $1$ 或 $0$ 权边）。
C++ 标准源码（最长路求最小值+正环判定模板）
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const int MAXN = 100005;
struct Edge {
int to;
long long weight;
};
std::vector<Edge> adj[MAXN];
long long dist[MAXN];
int cnt[MAXN]; // 记录每个节点入队的次数，用于检测环路
bool in_queue[MAXN]; // 标记节点是否在当前队列中
// SPFA 判定正环并计算最长路
bool spfa_longest(int n) {
std::queue<int> q;
// 初始化物理极值
for (int i = 0; i <= n; ++i) {
dist[i] = -INF;
cnt[i] = 0;
in_queue[i] = false;
}
// 从超级源点 0 出发
dist[0] = 0;
q.push(0);
in_queue[0] = true;
cnt[0] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
in_queue[u] = false;
for (size_t i = 0; i < adj[u].size(); ++i) {
int v = adj[u][i].to;
long long w = adj[u][i].weight;
// 最长路松弛方程
if (dist[u] + w > dist[v]) {
dist[v] = dist[u] + w;
if (!in_queue[v]) {
q.push(v);
in_queue[v] = true;
cnt[v]++;
// 致命踩坑点：入队次数达到或超过 N+1（加上超级源点共 N+1 个点）即代表存在正环
if (cnt[v] > n) {
return false; // 系统存在正环，代数矛盾，无解
}
}
}
}
}
return true; // 求解成功
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n, m;
if (!(std::cin >> n >> m)) return 0;
for (int i = 0; i < m; ++i) {
int opt, u, v;
long long c;
std::cin >> opt >> u >> v;
// 代数转化示例
if (opt == 1) { // u - v >= c => u >= v + c
std::cin >> c;
adj[v].push_back(Edge{u, c});
} else if (opt == 2) { // u - v <= c => v - u >= -c => v >= u - c
std::cin >> c;
adj[u].push_back(Edge{v, -c});
} else if (opt == 3) { // u == v => u >= v + 0 且 v >= u + 0
adj[v].push_back(Edge{u, 0});
adj[u].push_back(Edge{v, 0});
}
}
// 建立超级源点 0，标定隐含约束：每个变量 $x_i \ge 0$，即 $x_i \ge x_0 + 0$
for (int i = 1; i <= n; ++i) {
adj[0].push_back(Edge{i, 0});
}
if (!spfa_longest(n)) {
std::cout << "No Solution\n";
} else {
long long total_min = 0;
for (int i = 1; i <= n; ++i) {
total_min += dist[i];
}
std::cout << total_min << "\n";
}
return 0;
}NOIP 实战避坑指南
- 环路判定阈值未考虑超级源点：
差分约束建图通常需要引入虚拟超级源点（通常为 $0$ 号点），这意味着整个图的实际节点总数变为了 $N + 1$。如果选手的环路终止判定条件依然盲目写成
if (cnt[v] >= n)，在图本身是一个包含了所有原节点的完整大环时，会触发提前误判，将合法解判定为无解。标准阈值必须是cnt[v] > n。 - 隐藏约束条件漏建图： 许多题目不会显式给出所有变量的界限。例如题目暗示“每个人至少分到 1 个苹果”，这意味着隐含了约束 $x_i \ge 1$，即 $x_i - x_0 \ge 1$。如果漏掉了这些隐含约束，图的各个孤立连通块没有底座标定，SPFA 跑出的结果将是无约束的极值（如 $-\infty$ 或错解），在赛场上会直接痛失绝大部分分数。
经典 NOIP/洛谷 真题
1. 洛谷 P5960 【模板】差分约束系统
- 题意描述：
给定一个包含 $N$ 个变量和 $M$ 个不等式的系统，每个不等式形如 $x_{c_1} - x_{c_2} \le y$。求一组可行解，使得所有不等式同时满足。如果无解输出
NO。 - 问题本质与核心思路：
标准最短路差分约束模板。
将 $x_{c_1} - x_{c_2} \le y$ 转换为标准型 $x_{c_1} \le x_{c_2} + y$，从 $c_2$ 向 $c_1$ 连一条权值为 $y$ 的有向边。由于是求可行解，任选最短路或最长路均可。建立超级源点 $0$ 向各个点连权值为 $0$ 的边，跑一次标准 SPFA 最短路。若检测到负环则输出
NO；否则，最终的 $dist[i]$ 向量本身就是一组完全合法的代数解。
2. 洛谷 P3275 [SCOI2011] 糖果
- 题意描述： 幼儿园有 $N$ 个小朋友，老师要分糖果。有 $M$ 个限制条件，形如：“A 必须比 B 多”、“A 不能比 B 少”等。每个小朋友至少要分到 1 个糖果。求老师至少需要准备多少个糖果。如果无法满足则输出 -1。
- 问题本质与核心思路：
最长路差分约束的硬核变形题。
求“至少”需要多少糖果，本质是求代数系统的最小值，因此整体采用最长路建图。
条件拆解：“A不能比B少”即 $x_A \ge x_B$，连边 $B \to A$，权值为 0；“A必须比B多”即 $x_A \ge x_B + 1$，连边 $B \to A$，权值为 1。
隐含条件：每个小朋友至少 1 个糖果，即 $x_i \ge 1$，由超级源点 $0$ 向所有点 $i$ 连一条权值为 1 的边。利用 SPFA 跑最长路，若发现正环则说明条件冲突，输出 -1。否则，$\sum_{i=1}^N dist[i]$ 即为最终答案。注意，糖果总数极易超过
int范围，必须强制使用long long累加。