Chgtaxihe's blog Chgtaxihe's blog
首页
练习
算法学习
读书笔记
小玩意

Chgtaxihe

首页
练习
算法学习
读书笔记
小玩意
  • 数论

  • 动态规划

  • 暴力

  • 图论

    • 2-SAT学习笔记
      • 模板题 洛谷P4782
    • 最短路学习笔记
    • KM学习笔记
    • 一般图最大匹配学习笔记
    • 二分图匹配学习笔记
    • 可撤销并查集学习笔记
    • 多源最短路学习笔记
    • 斯坦纳树学习笔记
    • 最小异或生成树学习笔记
    • LCA学习笔记
    • 树的直径与重心
    • 树的重心
    • 矩阵树定理学习笔记
    • 网络流-最小割学习笔记
    • 网络流-最小费用最大流学习笔记
  • 数据结构

  • 字符串

  • 几何

  • 博弈论

  • 其他

2-SAT学习笔记

# 2-SAT

有nnn个布尔x1...xnx_1...x_nx1​...xn​,另有mmm个限制条件用以限制xix_ixi​与xjx_jxj​之间的关系。要求求出一组可行解。

2-SAT就是用来解决以上问题的工具。

# 模板题 洛谷P4782

我们对xix_ixi​、¬xi\neg x_i¬xi​分别建一个点,那么xi∨yix_i \lor y_ixi​∨yi​就可表示为两条边:¬xi→yi\neg x_i \to y_i¬xi​→yi​和¬yi→xi\neg y_i \to x_i¬yi​→xi​

那么我们要怎么表示限制条件xi=truex_i=truexi​=true呢?只需让建边¬xi→xi\neg x_i \to x_i¬xi​→xi​即可


得到这么一幅图之后,显然在同一个强连通分量里面的点要么都选,要么都不选

于是我们用Tarjan跑一边强连通分量,如果xix_ixi​与¬xi\neg x_i¬xi​在同一个强连通分量,说明无解


对于有解的情况,只需输出xix_ixi​和¬xi\neg x_i¬xi​中拓扑序更大的一个即可。

这样能够保证得到解。因为如果存在边a→ba \to ba→b,那么一定存在另一条边¬b→¬a\neg b \to \neg a¬b→¬a,因此......(证明略)

(PS.如果用Tarjan"染色"的话,记得得到的颜色是反过来的拓扑序)

AC代码如下:

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e6 + 1e3;

int dfn[maxn], low[maxn], steck[maxn], color[maxn]={0};
int color_cnt=0, dfs_n=0, top=0;
stack<int> stk;
vector<int> G[maxn];

void tarjan(int u){
    low[u] = dfn[u] = ++dfs_n;
    stk.push(u);
    for(int v:G[u]){
        if(!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }else if(!color[v]){
            low[u] = min(low[u], low[v]);
        }
    }
    if(low[u] == dfn[u]){
        color_cnt++;
        do{
            u = stk.top(); stk.pop();
            color[u] = color_cnt;
        }while(low[u] != dfn[u]);
    }
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, m, x, a, y, b;
    cin >> n >> m;
    for(int i=0; i<m; i++){
        cin >> x >> a >> y >> b; // x=a or y=b
        G[x + (a^1)*n].push_back(y + b*n); // not x=a then y=b
        G[y + (b^1)*n].push_back(x + a*n); // not y=b then x=a
    }
    for(int i=1; i<=(n<<1); i++) if(!dfn[i]) tarjan(i);
    for(int i=1; i<=n; i++) {
        if(color[i] == color[i+n]){
            cout << "IMPOSSIBLE\n";
            return 0;
        }
    }
    cout << "POSSIBLE\n";
    for(int i=1; i<=n; i++){
        cout << (color[i]>color[i+n]) << " ";
    }
    cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

# 参考资料

2-SAT略解 (opens new window)

题解 P4782 【【模板】2-SAT 问题】 (opens new window)

上次更新: 2021/02/24, 03:37:30
高斯消元学习笔记
最短路学习笔记

← 高斯消元学习笔记 最短路学习笔记→

最近更新
01
深入理解Java虚拟机
03-04
02
DNS工作原理
02-27
03
改用VuePress啦
02-23
更多文章>
Theme by Vdoing | Copyright © 2019-2021
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式