wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

图论

图的连通性

有向图的强连通分量

无向图的割点割边和双连通分量

流和匹配

最大流

最大流的一些应用

最小割

费用流

带上下界的网络流

二分图匹配

二分图最大权匹配

网络流综合

图论杂项

最大团搜索算法

树上问题

kruskal重构树

kruskal重构树的一些问题

最小生成树

最短路

差分约束

2-SAT

[[ item.c ]]

2-SAT

## 2-SAT 概念
给定$$n$$个**布尔变量**$$x_1, x_2, \cdots, x_n$$，每个变量都是`{0, 1}`
给定若干 **clause**，如下描述

1）$$x_1 \textbf{ or } (\textbf{not } x_2) = 1$$
即$$x_1 = 1 \textbf{ or } x_2 = 0$$**至少有一个成立**

2）$$x_1 \textbf{ and } x_2 = 0$$
即$$x_1 = 0$$或者$$x_2 = 0$$至少有一个成立

3）$$x_1 = x_2$$，可以拆成
$$x_1 = 1, x_2 = 0$$至少一个成立
$$x_1 = 0, x_2 = 1$$至少一个成立

4）$$x_1 = 1$$，拆成
$$x_1 = 1, x_1 = 1$$至少一个成立

问能不能构造出一组解

## 2-SAT算法
![](/media/content_img/2SAT-01.png)
![](/media/content_img/2SAT-02.png)

## 满汉全席
**[P4171 [JSOI2010] 满汉全席](https://www.luogu.com.cn/problem/P4171)**
有`n`种材料，每一种材料有`2`种做法，要么是满式料理，要么是汉式料理
然后给`m`个条件，给定条件，`m1`表示第一种材料要做成满式料理，`h2`表示第`2`种材料要做成汉式料理
这两个至少有一个要满足

**算法分析**
这是一个`2-SAT`的模版题，`2`种条件，至少要有一个满足
```bash
// 2-SAT
void solve(int cas) {
    // [0, 2n - 1], x -> 2x, x -> 2x + 1
    // mi in(i), hi out(i)
    int N = 2 * n;
    SCC scc(N);
    for (int i = 0; i < m; i++) {
        // X 和 Y 至少有一个满足
        int X = 2 * x + (sa[0] == 'h');
        int Y = 2 * y + (sb[0] == 'h');

scc.addEdge(X ^ 1, Y);
        scc.addEdge(Y ^ 1, X);
    }

scc.work();

for (int x = 0; x < n; x++) {
        int X = 2 * x, Y = 2 * x + 1;
        // if bel[X] < bel[Y]，选 X，否则选 Y
        if (scc.bel[X] == scc.bel[Y]) {
            cout << "BAD\n";
            return;
        }
    }
    cout << "GOOD\n";
}
```
## 奶牛议会
**[P3007 [USACO11JAN] The Continental Cowngress G](https://www.luogu.com.cn/problem/P3007)**
有`n`个议案，每个议案要么通过，要么不通过，有`m`个限制
表示赞成一个议案，或者反对另外一个议案
要求每个奶牛投出的`m`个限制，至少要有一个和最终结果符合

判断有没有解，如果无解输出`impossible`
否则对于每个议案，如果在所有的方案里面都通过，输出`Y`，都不通过输出`N`
否则输出`?`

**算法分析**
> 方法一

判断有没有解，就是`2-SAT`，现在就是判断会不会**恒为真，或者恒为假**
如果要判断恒为真，那么就在原图的基础上，从$$x_i \to \neg x_i$$连一条边
再跑一遍`SAT`，对每个点$$i$$都建这样的新图，$$O(nm)$$可以解决

> 方法二

在原图的基础上做，如果存在路径$$x_i \to \neg x_i$$，那么根据`2-SAT`的构造
此时我们应该选$$\neg x_i$$，也就是说$$x_i$$**恒为假**，反之$$\neg x_i \to x_i$$
那么$$x_i$$就**恒为真**，如果$$x_i, \neg x_i$$**不可达**，说明是`?`（都可以）

因为不可达，你加一条边也不会成环，也不会形成新的`SCC`，`SCC`不会变
原来有解，现在还是有解的

对每个$$i$$，针对$$x_i, \neg x_i$$判可达关系即可

## NOI2017游戏
**[P3825 [NOI2017] 游戏](https://www.luogu.com.cn/problem/P3825)**
进行`n`场游戏，每场游戏使用一张地图，小 L 有三辆赛车`A, B, C`
地图有四种，分别是`x, a, b, c`，有若干限制

地图`a`只能跑赛车`B, C`，地图`b`只能用`A, C`，地图`c`只能用`A, B`，地图`x`什么赛车都可以用
`x`不常见，最多只有`8`张

`n`场游戏的地图可以用一个小写字母组成的字符串表示，比如`S = xaabxcbc`
也有一些要求，$$(i, h_i, j, h_j)$$，也就是说$$i$$场使用了型号$$h_i$$的车子
那么第$$j$$场就要使用型号$$h_j$$的车子，输出方案，无解输出`-1`

**算法分析**
> 这里$$d$$很小，范围是$$0 \leqslant d \leqslant 8$$，先考虑`d = 0`怎么做，也就是说没有地图$$x$$

那么条件可以表示为
```bash
a: {B, C}
b: {A, C}
c: {A, B}

针对地图来考虑，每种地图只能用 种类1 或者 种类2 的赛车
这就是一个 2-SAT
```
四元组其实也是有一个**推理关系的**
```bash
i 选了 h(i) ---> j 必须选 h(j)
j 不选 h(j) ---> i 不选 h(i)

（逆否命题要加上）
```
> 现在考虑，有$$x$$限制要怎么做？

因为$$x$$地图的数量非常小，可以用$$O(3^8)$$枚举，每个$$x$$对应哪个值
剩下的地图，跑`2-SAT`，但是$$O(3^8) O(n)$$，复杂度还是有点高
```bash
实际上，x 可以写成
x: {AB, AC, BC}
那么注意到，此时可以将 x 更换赛道

1）如果 x = { 赛道 a }，那么 x 已经把用赛车 BC 都考虑进去了
2）如果 x = { 赛道 b }，那么 x 已经把用赛车 AC 都考虑进去了
```
综上，可以$$2^d$$枚举，$$x$$改成`{a or b}`，比如说二进制压缩，`mask >> j & 1`
那么`对应的 x`就改成`a`，反之改成`b`

这样仍然可以用`2-SAT`来处理

**2-SAT 连边，遇到非法的情况**
实际上，比如给出的$$(i, h_i)$$，$$h_i$$不合法，那么就不需要连边
而如果$$(i, h_i, j, h_j)$$，$$h_j = -1$$，也就是$$h_j$$非法，但$$h_i$$合法呢？
那么$$h_i$$**永远不能选！**，也就是说，$$h_i \to \neg h_i$$连边

> 输出方案

关键是把**道路的标号**和**车的标号**相对应，处理`2-SAT`限制，连边的时候也是如此
比如$$(i, h_i)$$，有可能`h[i]`在跑道$$i$$上不能用

对`i`拆点，用了$$h_i$$和不用$$h_i$$，拆成$$i, i^{\prime}$$

```bash
int getid(跑道编号，车的编号 hi) {
	if (跑道编号 = 车的编号) return -1
	否则，如果 s[i] = 'a' + (hi+ 1) mod 3, return 2 * i
	如果 s[i] = 'a' + (hi + 2) mod 3， return 2 * i + 1
}
```
输出方案的时候，如果`bel[2x] < bel[2x + 1]`，那么选`2x`
对应车的编号应该是`(s[x] - 'a') + (-1) mod 3`

### 算法实现
```bash
void solve(int cas) {
    // 输入道路信息省略
    using arr = array<int, 4>;
    vector<arr> cond;

for (int k = 0; k < m; k++) {
        int i, j;
        char hi, hj;
        cin >> i >> hi >> j >> hj;
        i--, j--;

cond.emplace_back(arr{i, hi - 'A', j, hj - 'A'});
    }
    vector<int> X;
    for (size_t j = 0; j < str.size(); j++) {
        if (str[j] == 'x') X.emplace_back(j);
    }

int N = 2 * n;

vector<char> ans(n);

auto check = [&]() -> bool {
        SCC scc(N);

auto getid = [&](int i, int hi) -> int {
            if (str[i] == 'a' + hi) return -1;
            if (str[i] == 'a' + (hi + 1) % 3) return 2 * i;
            if (str[i] == 'a' + (hi + 2) % 3) return 2 * i + 1;

assert(0);
            return -1;
        };

for (auto [i, hi, j, hj] : cond) {
            auto x = getid(i, hi), y = getid(j, hj);
            if (x != -1 and y != -1) {
                scc.addEdge(x, y);
                scc.addEdge(y ^ 1, x ^ 1);
            }
            else if (y == -1 and x != -1) {
                scc.addEdge(x, x ^ 1);
            }
        }
        scc.work();

for (int i = 0; i < n; i++) {
            if (scc.bel[2 * i] == scc.bel[2 * i + 1]) return false;
        }

for (int i = 0; i < n; i++) {
            if (scc.bel[2 * i] < scc.bel[2 * i + 1]) {
                ans[i] = (str[i] - 'a' + 2) % 3 + 'A';
            }
            else {
                ans[i] = (str[i] - 'a' + 1) % 3 + 'A';
            }
        }

return true;
    };

for (int mask = 0; mask < (1 << d); mask++) {
        for (int j = 0; j < d; j++) {
            auto i = X[j];
            str[i] = (mask >> j & 1) ? 'a' : 'b';
        }

if (check()) {
            for (auto c : ans) cout << c;
            cout << "\n";
            return;
        }
    }

cout << "-1\n";
}
```

看完文章有啥想法

算法小站

wiki 主题

图论

2-SAT

目录