负环、差分约束与2-SAT
数形结合的艺术
前置知识
本次学习需提前掌握以下两个最短路算法的核心思想与基础实现：
- Bellman-Ford 算法
- SPFA 算法
一、Bellman-Ford 算法
1. 代码实现
int n, m, s;
vector<pair<int, int>> e[N];
int dis[N];void ford() {memset(dis, 0x3f, sizeof(int) * (n + 1));dis[s] = 0;for (int k = 1; k < n; k++) {bool flag = 0;for (int u = 1; u <= n; u++)for (auto [v, w] : e[u])if (dis[v] > dis[u] + w)dis[v] = dis[u] + w, flag = 1;if (!flag) return;}
}
2. 核心理解
算法通过\(n-1\) 轮全局松弛操作求解单源最短路，其中 \(n\) 为图的节点数。
- 松弛操作：对边 \(<u,v,w>\)，若 \(dis[v] > dis[u]+w\)，则更新 \(dis[v] = dis[u]+w\)；
- 提前退出：用
flag标记本轮是否发生松弛，若无松弛说明最短路已确定，可直接退出。
二、SPFA 算法
1. 代码实现
int n, m, s;
vector<pair<int, int>> e[N];
int dis[N];
bool vis[N];
queue<int> q;void SPFA() {memset(dis, 0x3f, sizeof(int) * (n + 1));dis[s] = 0;q.emplace(s);while (q.size()) {int u = q.front(); q.pop();vis[u] = 0;for (auto [v, w] : e[u])if (dis[v] > dis[u] + w) {dis[v] = dis[u] + w;if (!vis[v]) q.emplace(v), vis[u] = 1;}}
}
2. 与 Dijkstra 算法的核心区别（负权边处理）
（1）Dijkstra 无法处理负权边的原因
Dijkstra 采用贪心策略，认为当前找到的最短路节点的距离值不再更新，但若存在负权边，后续遍历可能得到更短的路径，打破贪心的前提。
（2）SPFA 能处理负权边的原因
SPFA 是 Bellman-Ford 的队列优化，节点可以多次入队、边可以多次松弛，直到图中不存在可松弛的边为止，能适配负权边的场景。
（3）时间复杂度
SPFA 时间复杂度无严格保证，最坏情况下与 Bellman-Ford 一致，为 \(O(nm)\)（\(m\) 为边数）。
三、负环
1. 负环的定义
给定有向图 \(G=(V,E)\)，若存在一个环 \(C\)，满足环上所有边的权值之和 \(\sum_{<u,v,w>\in C} w < 0\)，则称该环为负权环（简称负环）。
2. 负环与最短路的关联
使用 Bellman-Ford 求最短路时，若图中存在负环且负环能从源点到达，则第 \(n\) 轮仍能进行松弛操作（因为负环可无限松弛，使节点距离不断减小）。
3. Bellman-Ford / SPFA 求解负环
- Bellman-Ford 判负环：执行 \(n\) 轮松弛，若第 \(n\) 轮仍能松弛，说明图中存在负环；
- SPFA 判负环：统计每个节点的入队次数，若某节点入队次数 \(\ge n\)，说明图中存在负环（核心思路：正常最短路中节点入队次数最多为 \(n-1\)）。
四、差分约束问题
1. 问题核心
差分约束问题是一类不等式组求解问题，给定一组形如 \(x_i - x_j \le c\)（\(c\) 为常数）的不等式，求变量 \(x_1,x_2,\dots,x_n\) 的一组可行解。
2. 核心转换（不等式 \(\to\) 图的边）
对差分不等式 \(x_i - x_j \le c\)，变形为 \(x_i \le x_j + c\)，与最短路的松弛条件 \(dis[i] \le dis[j] + w\) 一致，因此：
- 建立有向边 \(<j,i,c>\)；
- 新增超级源点 \(0\)，对所有节点 \(k\) 建立边 \(<0,k,0>\)（保证图的连通性，令 \(x_0=0\)）。
3. 求解步骤（跑图）
- 将所有差分不等式转换为对应的有向边，构建图结构；
- 以超级源点为起点，运行 Bellman-Ford 或 SPFA 求解最短路；
- 若图中存在负环，则不等式组无解；若不存在负环，\(dis[1],dis[2],\dots,dis[n]\) 即为一组可行解。
4. 无解的判定
差分约束问题无解的充要条件是：转换后的图中存在负环（负环对应矛盾的不等式组，无法满足所有约束）。
五、2-SAT 问题
1. 问题核心
2-SAT 问题是一类逻辑判定问题，给定 \(n\) 个布尔变量 \(x_1,x_2,\dots,x_n\)（取值为真/假），以及若干形如\(x_a\) 为真 或 \(x_b\) 为真的逻辑条件，判断是否存在变量的赋值方案满足所有条件，若存在则求出一组可行解。
2. 核心逻辑转换（条件 \(\to\) 有向边）
2-SAT 的关键是将或条件转换为蕴含条件，对条件「\(A\) 成立 或 \(B\) 成立」（\(A,B\) 为变量的真假判定）：
- 等价于「\(A\) 不成立 \(\implies B\) 成立」；
- 等价于「\(B\) 不成立 \(\implies A\) 成立」。
3. 图的构建规则
对每个布尔变量 \(x_i\)，建立两个节点表示其两种状态：
- \(i\)：表示 \(x_i\) 为真（成立）；
- \(i'\)（或 \(i+n\)）：表示 \(x_i\) 为假（不成立）。
对蕴含关系「\(P \implies Q\)」，建立有向边 \(<P,Q>\)，表示若 \(P\) 成立则 \(Q\) 必须成立。
4. 可行性判定（SCC 判定）
对构建的有向图，求其所有强连通分量（SCC）：
- 若存在某个变量 \(x_i\)，满足 \(i\) 和 \(i'\) 属于同一个强连通分量，则 2-SAT 问题无解；
- 若所有变量的两个状态节点都分属不同的强连通分量，则问题有解。
5. 可行解的求解（拓扑序 / Tarjan 编号）
（1）缩点建 DAG
将每个强连通分量缩为一个节点，得到新的有向无环图（DAG），DAG 满足拓扑序。
（2）拓扑序的核心结论
对变量 \(x_i\) 的两个状态节点 \(i\)（真）和 \(i'\)（假）：
- 若在 DAG 的拓扑序中，\(i'\) 出现在 \(i\) 之前，则取 $x_i = $ 真；
- 否则取 $x_i = $ 假。
逻辑推导：因「真只能推导出真」，若 \(i'\) 拓扑序在前，若取 \(i'\) 为真则无法推导出 \(i\) 为真，产生矛盾，故只能取 \(i'\) 为假、\(i\) 为真。
（3）Tarjan 算法的便捷性
Tarjan 算法求强连通分量时，得到的SCC 编号天然满足逆拓扑序，因此简化结论：
- 若 \(i\) 的 SCC 编号 \(<\) \(i'\) 的 SCC 编号，则取 $x_i = $ 真；
- 否则取 $x_i = $ 假。