学习笔记 - 2sat | Lucky_Glass's Blog

以心为名，名为爱惜

0%

学习笔记 - 2sat

发表于 更新于 分类于 Valine：

noip考完，既轻松又无奈，回来慢慢填坑
这篇博客也是拖了好久，通过kuangbin的博客才弄懂2-sat的

2-sat问题

先说sat问题——指一种每个变量只有两个值（true or false），并且给出一些限制，每个限制的基本形式为：

$a XOR/OR/AND b XOR/OR/AND c (etc.) = true$

另外当每个限制涉及的变量只有两个时，这类问题称为2-sat问题，即 $a XOR/OR/AND b=true$，当然也可以限制值为 false，在这里a,b也可以不保证不同。求这样的问题的解，即每一个变量选或不选。

2-sat问题的建模

假设现在有N个变量形成2-sat问题。

由于一个变量要么为true，要么为false；我们可以把变量拆分成两个点——一个点表示true，另一个表示false，这样一来我们有 2N 个点，也就是 N 个点对；下面我们称 A、A’ 分别表示变量A选、不选。然后我们称“一个变量的状态”为“这个状态所对应的点选或不选”。

我们可以将点连边，边(X,Y)表示选X就必须选Y；下面举两种最基本的例子：

①选变量A就必须选变量B，则连 (A,B) (B’,A) 两条有向边；
②必须选变量A，则连 (A’,A) 的有向边；

1-可行性问题求解

即判断某一方案是否可行。常用于检验二分答案。

通过求强连通分量求解——如果 点v 和 点v’ 同时存在于一个强连通分量中，则说明从“选 变量v” 这一起点出发，可以推导出“不选 变量v”（反过来说也一样），这样就是不合法的。换句话说，点v 和 点v’ 不能在同一个强连通分量中。

求强连通分量的话这里就用一个常规的方法——先从某个点出发DFS遍历能够到达的点，当退出一个DFS函数时，将当前的点压入队列中（建议手写队列，因为这里只是用来储存变量）。

上面是DFS1，每个点只能遍历一次。

然后依次访问队列中的点，然后从当前枚举到的队列中的点X出发进行DFS，将遍历到的点所属的“块”(blk)都设为与点X相同的“块”。这样一个“块”就是一个强连通分量。

最后枚举每一个变量i，检查 点i 和 点i’ 是否在一个强连通分量中，如果存在，则不可行。

举个例子：HDU 3622 Bomb Game

[题意]

你需要在平面上放n个炸弹——放置第i个炸弹时，你需要在$(Ax_i,Ay_i)$和$(Bx_i,By_i)$两个位置中选择一个位置放置。每个炸弹的爆炸半径都是k，任意两个炸弹的爆炸范围不能重叠（可以相切）。求k最大为多少。

[解析]

很容易想到二分答案，放置第i个炸弹时选择 第一个位置 定义为“选择i”，选择第二个位置 定义为“不选择i”，这样就形成了一个2-sat问题。

根据二分出来的k可以求出重叠的炸弹，如果炸弹i与炸弹j重叠，则说明放炸弹i就不能放炸弹j，根据这个连边，2-sat判断合法性即可。

[源代码]

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
/*Lucky_Glass*/
#include<bits/stdc++.h>
using namespace std;
const int N=100,M=40000;
const double EPS=1e-5;
int n;

struct POINT{
	int x,y;
}s[N*2+5];
inline double Dist2(int a,int b){
	return 1.0*(s[a].x-s[b].x)*(s[a].x-s[b].x)+1.0*(s[a].y-s[b].y)*(s[a].y-s[b].y);
}

struct EDGE{
	int to,nxt;
}edg1[M+5],edg2[M+5];
int hed1[N*2+5],hed2[N*2+5];
int cnt1,cnt2;
void AddEdge(int u,int v){ //连边，正反图都要连
	edg1[cnt1].to=v;
	edg1[cnt1].nxt=hed1[u];
	hed1[u]=cnt1++;
	edg2[cnt2].to=u;
	edg2[cnt2].nxt=hed2[v];
	hed2[v]=cnt2++;
}
void ClearMap(){ //清空图
	memset(hed1,-1,sizeof hed1);
	memset(hed2,-1,sizeof hed2);
	cnt1=cnt2=0;
}

int Pop[N*2+5],blk[N*2+5];
bool vis[N*2+5];
int blkcnt;
void DFS1(int u){ //求出每个点退出DFS的顺序
	vis[u]=true;
	for(int i=hed1[u];i!=-1;i=edg1[i].nxt)
		if(!vis[edg1[i].to])
			DFS1(edg1[i].to);
	Pop[++Pop[0]]=u;
}
void DFS2(int u){ //求强连通分量
	vis[u]=true;blk[u]=blkcnt; //blk[i]表示i所属的联通块编号
	for(int i=hed2[u];i!=-1;i=edg2[i].nxt)
		if(!vis[edg2[i].to])
			DFS2(edg2[i].to);
}
bool Check(){
	Pop[0]=blkcnt=0;
	memset(vis,false,sizeof vis);
	for(int i=0;i<2*n;i++)
		if(!vis[i])
			DFS1(i);
	memset(vis,false,sizeof vis);
	for(int i=Pop[0];i>=1;i--) //按照退出顺序
		if(!vis[Pop[i]]){
			blkcnt++;
			DFS2(Pop[i]);
		}
	for(int i=0;i<n;i++)
		if(blk[i*2]==blk[i*2+1]) //如果不合法
			return false;
	return true;
}

int main(){
	while(~scanf("%d",&n)){
		for(int i=0;i<n;i++)
			for(int j=i*2;j<=i*2+1;j++)
				scanf("%d%d",&s[j].x,&s[j].y);
		double lef=0,rig=40000.0;
		while(rig-lef>=EPS){
			double mid=(lef+rig)/2;
			ClearMap();
			for(int i=0;i<n*2;i++) //O(n^2)连边 :)
				for(int j=i%2? i+1:i+2;j<2*n;j++)
					if(Dist2(i,j)<4*mid*mid)
						AddEdge(i,j^1),
						AddEdge(j,i^1);
			if(Check()) lef=mid;
			else rig=mid;
		}
		printf("%.2lf\n",rig);
	}
	return 0;
}

(坑还没填完，下一个弄懂再写 TAT)
更新-$2018/11/17$；终于把后面一道题弄懂了

另外一个例子……POJ 3207 Ikki’s Story IV - Panda’s Trick

想法比较丰富……另外写一个blog……

The End

Thanks for reading!

Email: lucky_glass@foxmail.com ，欢迎提问~