有 个布尔变量 ,另有 个需要满足的条件,每个条件的形式都是「 为 true / false 或 为 true / false」。比如「 为真或 为假」、「 为假或 为假」。
2-SAT 问题的目标是给每个变量赋值使得所有条件得到满足。
算法流程
1. 逻辑关系:把 或关系 转化为 蕴含关系
- 成立 或 成立,等价于:若 不成立,则 必成立;且 若 不成立,则 必成立。
- 注意: 蕴含关系具有传递性:若 ,则 。蕴含关系通常是不可逆的。
2. 拆点建图
把每个变量看成点,把 个点拆成 个点,即把 拆成 和 :
- 对应
- 对应
建图就是连有向边,例如:,其中 。
- 蕴含关系 可以表示为:从 到 的有向边。
- 蕴含关系 可以表示为:从 到 的有向边。
3. Tarjan 缩点
先跑 Tarjan 缩点,缩点后判断:
- 如果 和 在同一 SCC 里(即在一个环内),那么显然无解。因为 不能既取 0 又取 1。
- 否则, 和 可能在一条链上或无关,那么一定存在可行解。
如何构造答案?
1. 核心构造规则
在完成 Tarjan 缩点并判定无解(即不存在 与 在同一 SCC)后,变量的赋值规则为:
- 若
scc[x] < scc[not_x],则令 ; - 若
scc[x] > scc[not_x],则令 。
关键背景: Tarjan 算法得到的 SCC 编号是 反拓扑序。编号越小,在拓扑序中越靠后(越接近推导链的终点/汇点)。
2. 为什么这样是对的
- 推导性质: 若存在推导 ,则 为真时 必为真。
- 拓扑逻辑: 越靠近汇点(拓扑序后)的点,其约束越少。将汇点设为真,不会通过边传递“必须为真”的压力给其他点;而将源点(拓扑序前)设为真,会引发连锁反应。
- 对称性: 蕴含图是对称的。如果 在拓扑序后端,其否定点 必然在拓扑序前端。
3. 正确性证明(反证法)
目标: 证明对于任意边 ,不存在 且 的情况。
证明过程:
- 前提条件:
- 有向边 图中必有逆否边 。
- 根据 Tarjan 序性质:
scc[u] >= scc[v]且scc[not_v] >= scc[not_u]。
- 假设冲突发生:
-
scc[u] < scc[not_u] -
scc[not_v] < scc[v]
-
- 链条推导: 将上述四个不等式连立:
- 结论: 推导出 ,矛盾。因此,该赋值规则下逻辑恒自洽。
4. 有点难理解的地方
Q1:路径 为什么不导致矛盾?
- 误区: 认为存在路径就会矛盾。
- 真相: 只有 环 () 才矛盾。
- 仅表示一种强约束:若 为真则产生矛盾,所以 只能取假。
- 在算法中, 在 的下游,
scc[not_x]较小,规则会正确地将 设为真,即 设为假。
Q2:假设 都为真,但存在 ,怎么办?
- 真相: 这种情况在数学上不存在。
- 如果 ,那么在全局拓扑序中, 必须排在 的前面。
- 如果你选了 为真(即 为假),那么根据推导链, 必须也被迫为假。
- 算法通过
scc编号的大小关系,强制保证了这种全局序。如果 都被赋为真,它们之间的所有路径(包括 )都不会违背逻辑。
常见命题约束的建图方式
2-SAT 建图的核心是把题面条件翻译成蕴含关系。对任意蕴含 ,需要同时加入其逆否命题 。原因是二者在命题逻辑中等价:若 成立时 必须成立,那么当 不成立时, 也不可能成立。
蕴含 的实际含义是“禁止 为真且 为假”。当前提 为假时,该限制没有被触发,所以 是合法的。这也是一般的 不能直接用并查集合并 与 的原因:并查集合并表示 ,会错误排除 。
常见建图模板如下:
| 约束 | 逻辑形式 | 建边 |
|---|---|---|
| 必须为真 | 加 | |
| 必须为假 | 加 | |
| 蕴含 | 加 与 | |
| 至少一个为真 | 加 与 | |
| 不能同时为真 | 加 与 | |
| 必须相同 | 加 、,并补逆否 | |
| 必须不同 | 加 、,并补逆否 |
若使用 与 表示互为否定的两个状态,可以把加边封装成:
auto rev = [&](int x) { return x ^ 1; };auto add_imp = [&](int u, int v) { g[u].push_back(v); g[rev(v)].push_back(rev(u));};其中 add_imp(u, v) 表示加入 ,并自动补上 。
例题:公司搬迁
题目重述
给定 个互不相同的员工工号 ,每名员工必须被分配到 座或 座。若工号为 的员工在 座,则工号为 的员工也必须存在并在 座;若工号为 的员工在 座,则工号为 的员工也必须存在并在 座。判断是否存在一种分配方案。
约束为 ,,测试组数 。
关键观察
每名员工只有两种互斥状态,令
由于每名员工必须且只能选择一栋楼, 与 互为否定命题。
若存在员工 满足 ,则题意给出
若不存在这样的员工,则 这个状态不合法,等价于
座约束同理。若存在员工 满足 ,则
否则
因此本题可以直接按 2-SAT 建图并跑 SCC。
但本题还可以用并查集判断。原因在于函数 满足 。若 存在,则遍历到 时得到 ,遍历到 时又得到 ,二者合起来是
这已经不是一般 2-SAT 的单向约束,而是等价约束。等价关系可以用并查集合并维护。 座对应的函数 同样满足该性质。
解析
标准 2-SAT 做法可以令
且 。按以下方式建图:
- 若 存在且对应员工为 ,添加 ;否则添加 。
- 若 存在且对应员工为 ,添加 ;否则添加 。
跑 SCC 后检查是否存在 与 同属一个强连通分量。
并查集做法利用“存在搭档时状态等价”的特殊性。若 存在且对应员工为 ,合并:
若 存在且对应员工为 ,合并:
若 不存在,员工 不能在 座,即 为假、 为真。引入两个特殊集合 与 表示状态被强制为真或假,则合并:
若 不存在,则合并:
处理完所有约束后,若 与 被合并,说明某个状态被同时强制为真和假,无解。若存在某个员工满足 与 被合并,说明该员工被要求同时在两栋楼,也无解。否则存在可行方案。
使用哈希表存储工号到员工下标的映射,可以在均摊 时间内判断搭档是否存在。每个员工只进行常数次并查集合并与查询,单组复杂度为 ,空间复杂度为 。
代码
#include <array>#include <bits/extc++.h>#include <bits/stdc++.h>#include <cctype>#include <functional>#define ll long long#define N 1005using namespace std;using namespace __gnu_pbds;ll ans;ll n, m, a, b;ll t;int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> t; while (t--) { auto solve = [&]() { cin >> n >> a >> b; vector<ll> s(n + 5, 0); unordered_map<ll, ll> id; for (int i = 1; i <= n; i++) { cin >> s[i]; id[s[i]] = i; } auto toa = [&](int x) { return x * 2; }; auto tob = [&](int x) { return x * 2 + 1; }; auto rev = [&](int x) { return x ^ 1; }; vector<int> fa(2 * n + 10, 0); for (int i = 1; i <= 2 * n + 4; i++) fa[i] = i; auto find = [&](auto &&self, int x) -> int { return fa[x] = (fa[x] == x ? fa[x] : self(self, fa[x])); }; auto merge = [&](int x, int y) { auto rx = find(find, x); auto ry = find(find, y); if (rx == ry) return; fa[rx] = ry; }; auto add = [&](int x, int y) { merge(x, y); merge(rev(x), rev(y)); };#define F 2 * n + 2#define T 2 * n + 3 for (int i = 1; i <= n; i++) { if (id.count(a - s[i])) { add(toa(i), toa(id[a - s[i]])); } else { merge(toa(i), F); merge(tob(i), T); } if (id.count(b - s[i])) { add(tob(i), tob(id[b - s[i]])); } else { merge(tob(i), F); merge(toa(i), T); } } if (find(find, T) == find(find, F)) { cout << "NO\n"; return; } for (int i = 1; i <= n; i++) { if (find(find, tob(i)) == find(find, toa(i))) { cout << "NO\n"; return; } } cout << "YES\n"; }; solve(); } return 0;}#include <algorithm>#include <bits/stdc++.h>#include <iterator>#include <queue>#include <set>#include <unordered_map>#define N 100005#define inf 0x3f3f3f3f3f3f3f3f#define ll long long#define pr pair<ll, ll>using namespace std;int n, m, q, ma, block;vector<vector<int>> map1;vector<ll> scc;const ll mod = 1e9 + 7;int main() { ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); cin >> m >> n; map1.assign(2 * n + 5, {}); scc.assign(2 * n + 5, 0); auto rev = [&](int x) { return x > n ? x - n : x + n; }; for (int i = 1; i <= m; i++) { char op1, op2; ll a, b; cin >> op1 >> a >> op2 >> b; if (op1 == '-') a += n; if (op2 == '-') b += n; map1[rev(a)].push_back(b); map1[rev(b)].push_back(a); } vector<ll> dfn(2 * n + 5, 0); vector<ll> low(2 * n + 5, 0); int tim = 0; stack<int> sta; vector<bool> insta(2 * n + 5, 0); auto tarjan = [&](auto &&self, int x) -> void { dfn[x] = low[x] = ++tim; sta.push(x); insta[x] = 1; for (auto v : map1[x]) { if (!dfn[v]) { self(self, v); low[x] = min(low[x], low[v]); } else if (insta[v]) low[x] = min(low[x], dfn[v]); } if (low[x] == dfn[x]) { int y = -1; block++; while (y != x) { y = sta.top(), sta.pop(); insta[y] = 0; scc[y] = block; } } }; for (int i = 1; i <= 2 * n; i++) { if (!dfn[i]) tarjan(tarjan, i); } vector<bool> ans(n + 5, 0); for (int i = 1; i <= n; i++) { if (scc[i] == scc[i + n]) { cout << "IMPOSSIBLE"; return 0; } if (scc[i] < scc[i + n]) { ans[i] = 1; } } for (int i = 1; i <= n; i++) { if (ans[i] == 1) cout << '+' << ' '; else cout << '-' << ' '; } return 0;}分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ,距今已过 74 天
部分内容可能已过时