2-SAT问题

众所周知,2-SAT即二元适配性问题,用于解决一类布尔方程的求值问题……

有 $n$ 个布尔变量 $x_1, x_2, …,x_n$,给定 $m$ 对冲突关系,形如 $x_i\And x_j=0$,问一组可行解。
$n\le 10^5, m\le 10^6$

拆点建图,对每个变量 $x_i$ 拆成两个点 $i$ 和 $i’$,前者表示“$x_i$ 为真”,后者表示“$x_i$ 为假”。则可以将冲突关系 $(x_i,x_j)$ 转化为偏序关系 $(i,j’)$ 和 $(j,i’)$,依此得到一张有向图,然后就可以按照处理偏序关系的思路去做了。

容易发现,对于一个偏序环上的点,如果取一个值为真,那么剩下的点取值也必然为真;于是可以得到解的存在性定理:该布尔方程有解当且仅当 $\forall i$,$i$ 和 $i’$ 不在同一个偏序环上。

如何求出一组可行解呢?贪心地想,对于 $i$ 和 $i’$,我们应该选择在新图中拓扑序大的那个将其设为真,因为这样可以最小化影响。注意到 tarjan 求出的 SCC 的编号即为新图拓扑序的反序,因此直接判断即可。

一道栗题

有 $n$ 个布尔变量 $x_1\sim x_n$,另有 $m$ 个需要满足的条件,每个条件的形式都是 「$x_i$ 为 true / false 或 $x_j$ 为 true / false」。比如 「$x_1$ 为真或 $x_3$ 为假」、「$x_7$ 为假或 $x_2$ 为假」。
试给每个变量赋值使得所有条件得到满足,无解输出 IMPOSSIBLE。
$n, m\le 10^6$

容易发现一共有三种本质不同的条件形式:

  1. $x_i=0|x_j=1$,等价于 $x_i\And \neg x_j=0$,连边 $(i,j),(j’,i’)$;
  2. $x_i=0|x_j=0$,等价于 $x_i\And x_j=0$,连边 $(i,j’),(j,i’)$;
  3. $x_i=1|x_j=1$,等价于 $\neg x_i\And \neg x_j=0$,连边 $(i’,j),(j’,i)$。

然后套用上面的做法就好了,代码如下:

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
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;

const int CN = 4e6 + 6;

int read(){
int s = 0,ne = 1; char c = getchar();
while(c < '0' || c > '9') ne = c == '-' ? -1 : 1, c = getchar();
while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
return s * ne;
}

class fs {public: int to,nxt; void init(int t,int n) {to = t, nxt = n;} } E[CN];
int hd[CN], ecnt = 0; void add(int x,int y) {E[++ecnt].init(y, hd[x]),hd[x] = ecnt;}

int n, m, du[CN];

int dfn[CN], low[CN], idx = 0, stk[CN], top = 0, bel[CN], bcnt = 0; bool ins[CN];
void dfs(int u){
dfn[u] = low[u] = ++idx, stk[++top] = u, ins[u] = true;
for(int k = hd[u]; k; k = E[k].nxt){
int v = E[k].to;
if(!dfn[v]) dfs(v), low[u] = min(low[u], low[v]);
else if(ins[v]) low[u] = min(low[u], low[v]);
}
if(low[u] == dfn[u]){
bcnt++; int pos = 0;
while(pos ^ u) pos = stk[top--], ins[pos] = false, bel[pos] = bcnt;
}
}

int main()
{
freopen("_in.in", "r", stdin);

n = read(), m = read();
while(m--){
int i = read(), a = read(), j = read(), b = read();
if(a ^ b){
if(a > b) swap(i, j), swap(a, b);
add(i, j), add(j + n, i + n);
}
else{
if(!a) add(i, j + n), add(j, i + n);
else add(i + n, j), add(j + n, i);
}
}

for(int i = 1; i <= (n << 1); i++) if(!dfn[i]) dfs(i);

bool flag = true;
for(int i = 1; i <= n && flag; i++) flag &= (bel[i] != bel[i + n]);

if(!flag) puts("IMPOSSIBLE");
else{
puts("POSSIBLE");
for(int i = 1; i <= n; i++) if(bel[i] < bel[i + n]) printf("1 "); else printf("0 ");
}
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×