2-SAT专题

本文从WordPress迁移而来, 查看全部WordPress迁移文章

2-sat的题目不多,难度也不算太大,原因是题目的模型比较浅白,不难看出来,但是2-sat本身的理论应该是有些难度的。2-sat的套路和方法比较固定,困难的是构图,因为要做到不重不漏。2-sat构图,就是往点里面加边,每一条边表示的是一个必然关系。网上有很多人总结了一系列的2-sat构图方法,列出了很多式子,我从来没背过,因为记不住,其实只要懂得了2-sat构图的原因,就可以构出来,那些枯燥的布尔运算式子太难记了

  1. 2-sat的常见类型

    1. 判断一个2-sat是否存在可行解(这类问题最简单)
    2. 判断有可行解后输出任意一组可行解即可(这类问题要深入理解2-sat的理论,虽然有模板可以照着打,但是没意义)
    3. 在一个模型里求一个最值,最大值,最小值,最大值最小,最小值最大,这些问题,一般需要二分答案,然后用2-sat判断
    4. 输出一个字典序最小的可行解,这个问题只找到了一题,是用dfs直接暴力求解的
  2. 2-sat的解题步骤

    1. 构图:这是千变万化的东西,但只要记住,加边加的都是必然关系就行了
    2. 对图求一次强连通分量(我的模板中都是使用tarjan,其他算法也行,只要能求出scc即可)
    3. 根据求出来的强连通分量判断是否存在可行解
    4. 输出任意一组可行解:对原图缩点后得到一个DAG,将这个DAG倒置即构成一个逆图,在这个逆图上进行一次拓扑排序,拓扑排序过程中给DAG的点染色,一开始点都是白色,可行解的点染红色,对立点染蓝色。拓扑排序后,输出所有染成红色的点,就是一组可行解

(以上的解题步骤只能这么粗略讲,因为要深入进去那是要读论文来解决的,这里只是做个记录)

2-sat模板(构图部分略,因为构图时不会有模板的。求scc -> 判断是否存在可行解 -> 重新构图构DAG的逆图 -> 对新图拓扑排序+染色 -> 根据染色结果输出答案(输出答案部分每个题目可能不同))

但不得注明一点,2-sat的模板其实主要的就是拓扑排序部分,求scc部分,使用scc模板就够了。

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

void Find_Ans(){ //根据染色结果找出可行解保存在ans中
ans.clear();
for(int u = 1; u <= bcnt; u++)
if(color[u] == 2){
for(int i = 0; i < 2*n; i++)
if(belong[i] == u)
ans.pb(i);
}
sort(ans.begin(),ans.end());
}

void topsort(){ //拓扑排序,给点染色
cl(color,0,sizeof(color));
while(!que.empty()) que.pop();
for(int i = 1; i <= bcnt; i++)
if(inde[i] == 0) que.push(i);
while(!que.empty()){
int u,v;
u = que.front(); que.pop();
if(color[u] == 0){ //还没染色的点,染成红色,对立点染蓝色
color[u] = 2; color[opp[u]] = 1;
}
for(int i = 0; i < ver[u].size(); i++){
v = ver[u][i]; inde[v]--;
if(!inde[v]) que.push(v);
}
}
}

void rebuild(){ //缩点后重新建图
for(int i = 1; i <= bcnt; i++){
ver[i].clear();
inde[i] = 0;
}
for(int i = 0; i < 2*n; i++)
for(int k = head[i]; k != -1; k = e[k].next){
int u = belong[i] , v = belong[e[k].v];
if(u == v) continue;
ver[v].pb(u); inde[u]++; //建逆图
}
}

bool check(){ //判断是否存在可行解
for(int i = 0; i < n ; i++){
if(belong[i<<1] == belong[i<<1|1])
return false;
else{//记录每个点的对立点,记录的是它们所在的连通分量
opp[belong[i<<1]] = belong[i<<1|1];
opp[belong[i<<1|1]] = belong[i<<1];
}
}
return true;
}

void tarjan(int u){
dfn[u] = low[u] = ++dcnt;
stack[++top] = u; ins[u] = true;
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v;
if(!dfn[v]){
tarjan(v);
low[u] = min(low[u],low[v]);
}
else if(ins[v])
low[u] = min(low[u],dfn[v]);
}
if(dfn[u] == low[u]){
++bcnt;
while(true){
int x = stack[top--];
ins[x] = false;
belong[x] = bcnt;
if(x == u) break;
}
}
}

void scc(){
dcnt = bcnt = top = 0;
cl(dfn,0,sizeof(dfn));
cl(ins,false,sizeof(ins));
for(int i = 0; i < 2*n; i++)
if(!dfn[i])
tarjan(i);
}


/*-------------------2-SAT模板部分----------------------*/
build(); //根据矛盾关系建图,不同题目建图函数不同,但方法是一样的
scc(); //对原图求强连通分量
if(!check()){ //判断是否存在可行解
puts("NO"); continue;
}
rebuild(); //缩点后重新建图
topsort(); //拓扑排序求一组可行解
Find_Ans(); //根据拓扑结果找一组可行解
/*-------------------2-SAT模板部分----------------------*/
  1. 构图后判断是否存在可行解

    • hdu 3062 Party

      入门题,纯模板,可以初步体会下2-sat怎么构图

    • poj 3905 Perfect Election

      题中给出了人和人之间的可选不可选关系,可以进一步体会2-sat的构图

    • hdu 1824 Let’s go home

      以acm组队为背景,一队3人,这和2-sat的一对一对的关系有点不符?仔细思考即可,更进一步体会构图

    • poj 3207 Ikki’s Story IV – Panda’s Trick

      这题想清楚哪些是图中的点,哪些是边,有助于灵活使用2-sat模型

    • poj 3678 Katu Puzzle

      不错的题目,似乎包含了所有2-sat可能的加边情况,可以研究这题,彻底理解2-sat加边的原则

    • hdu 4115 Eliminate the Conflict

      2011年成都区域赛的题目(2010成都也出了2-sat),这题构图有难度,题解中的构图方法给出的构图办法不同,题解中的方法需要加更多边,但个人认为更好理解

  2. 二分答案 + 2-sat判定

    • uva 1146 Now or later

      求最小值最大,二分答案,然后2-sat判断。通过本题进一步体会构图技巧,另外想想二分答案是为了什么,为什么要用2-sat判定

    • hdu 3715 Go Deeper

      2010成都赛题目,个人感觉此题模型算是隐藏地比较深,不容易想到是2-sat,从这题,联系一下2-sat的经典模型,想想到底应该设置什么为图中的点

    • hdu 3622 Bomb Game

      不难想,基本题

    • poj 2296 Map Labeler

      训练到这里,要看出这题是2-sat模型已经不难了,但是注意这题要思维严谨,讨论好各种情况,构图做到不重不漏

    • poj 2723 Get Luffy Out

      理清关系,钥匙和门,成对,不选和选

    • hdu 1816 Get Luffy Out *

      上面那题的升级版,想想,用这题的构图去解上面的题行不行,用上面的解下面的又行不行?想通了收获很大

    • poj 2749 Building roads

      个人感觉较难的题,前提是要读懂题目,充分考虑,讨论各种情况

  1. 输出可行解

    • poj 3683 Priest John’s Busiest Day

      输出任意一组可行解,前期的预处理比较麻烦,后期的输出也麻烦,不过2-sat模型不难看出

    • poj 3648 Wedding

      这题构图还是有些难度的,另外注意题意,输出的不是一组可行解,而刚好是可行解意外的点(注意一组可行解以外的点,可能也是一组可行解,或者不是)

    • hdu 1814 Peaceful Commission

      输出字典序最小的解,不能用求scc+拓扑,直接由构出来的原图,利用性质,dfs求解

记住2-sat的要点:构图是王道,加边需谨慎,加的都是必要边,存在可有可无的不要加。给出的关系中,一些是必然的,直接加进图中,一些是矛盾关系,转化为必然关系后再加进图中