很开心，图论的知识也是积少成多，回首往昔，我对图论的算法仅限于最短路算法($\text {dijkstra}$)和最小生成树($\text {kruskal&prime}$) 。今天来学学这个 $\text {2-SAT}$ 问题。
2-SAT简介
$\text {SAT}$ 是适定性（Satisfiability）问题的简称。一般形式为 k - 适定性问题，简称 k-SAT。而当 $k>2$ 时该问题为 NP 完全的。所以我们只研究 $k=2$ 的情况。
$\text {2-SAT}$，简单的说就是给出 个集合，每个集合有两个元素，已知若干个 ，表示 与 矛盾（其中 与 属于不同的集合）。然后从每个集合选择一个元素，判断能否一共选 个两两不矛盾的元素。显然可能有多种选择方案，一般题中只需要求出一种即可。(from OI WIKI)
我想上面说的也比我说的稍微清楚点了，那么他的现实意义是什么呢？比较常见的就是逻辑推导了。
告诉你现在有 A，B，C三个人，且A和B是男生，如果B是男生，那么C是女生。问你这三个人的性别分别是什么，我们很容易可以知道A，B为男，C为女。
现在主要就是让计算机去计算这个问题怎么办呢？首先有一点可以确定的就是，一个人不能既是男又是女。如果存在这样的断言：如果A是男，那么A是女，这样的话A只能是女，因为A不可能既是男又是女，这个规定就为我们解决 $\text {2-SAT}$ 问题提供了思路。
我们假设有 $n$ 个人，那么我们建一个 $2\times n$ 个点的有向图，第如果 $i\le n$ 那么第 $i$ 个点表示 $i$ 为男，$i>n$ 那么第 $i$ 个点表示第 $i-n$ 个人为女。$i\to j$有向边很显然表：如果选择点 $i$，那么一定要选择点 $j$，如果我们选择点 $i$ ，那么点 $i+n$ 或者是点 $i-n$ 一定不能被选中，否则我们就说点 $i$ 不能被选择。所以，如果 $i$ 与 $i$ 的对立面同时不能被选择，即它们在同一个强连通分量内，那么整个问题都是无解的，因为有一个人的性别无论怎么选始终无法满足要求。
一般情况下，解不唯一，我们通常只需要输出是否有解即可，因为如果输出方案的话它们还要设置check脚本。但是洛谷它还就搞了，神不神奇。
例题
洛谷P4782
典型的 $\text {2-SAT}$ 问题，需要注意的是，它这里每个给出的条件都是或的关系，我们需要转换成边，那么我们想想怎么转换成一条边？如果它的条件给了 $x=1 \ or\ y=1 $ 。那么 $x=1$ 和 $y=1$ 是没有什么关系的，因为 $x=1$ 的时候 $y$ 没有限制，可以为 $1$ 可以为 $0$。但是呢，如果 $x=0$ 则一定推的出 $y=1$ 因为两个必须有一个满足，一个不满足会导致另一个一定要满足。所以我们就把一个条件的反面连接到另一个条件，同样另一个条件的反面也连到这个条件。
得到了一张有向图之后呢，我们先跑 $\text {tarjan}$ 强连通分量，观察是否存在 $i\le n$ 使得 $i$ 和 $i+n$ 是否属于同一个强连通分量，如果是，则无解。如果不是，则有解。(敲黑板)，这里需要注意了啊，这里跑 $\text{tarjan}$ 需要跑 $2\times n$ 个点。如果选中 $i$ 发现产生冲突那么选择该时事件的对立面则一定不会发生冲突。这里我们跑 $\text{dfs}$ ，把与之相连的所有点都打上被选中的标记，如果存在两个状态同时被选中，则返回 $\text{false}$ 并且逐层回溯，如果到最后都没发生冲突则已选中的状态固定，继续去搜索没有被打标记的状态。直到所有的状态都有一个对应的值，最后输出这个状态。
标程
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
| #include<bits/stdc++.h>
#define maxn 2000005
using namespace std;
struct eee{
int next;
int to;
}edge[maxn<<1],e[maxn<<1];
int root[maxn],root2[maxn],dfn[maxn],low[maxn],degree[maxn],vis[maxn],num[maxn],s[maxn],cnt,tot,top,cnt2,deep,n,m;
int sel[maxn];
void add(int x,int y){
edge[++cnt]={root[x],y};
root[x]=cnt;
}
void add2(int x,int y){
e[++cnt2]={root2[x],y};
root2[x]=cnt2;
}
void tarjan(int u){
dfn[u]=low[u]=++deep;
s[++top]=u;
vis[u]=1;
for(int i=root[u];i;i=edge[i].next){
int v=edge[i].to;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[v],low[u]);
}
else if(vis[v]){
low[u]=min(low[u],low[v]);
}
}
if(low[u]==dfn[u]){
vis[u]=0;
num[u]=++tot;
while(s[top]!=u){
vis[s[top]]=0;
num[s[top--]]=tot;
}
top--;
}
}
int dfs(int u){
sel[u]=1;
if(sel[(u-1)%n+1]&&sel[(u-1)%n+n+1]){
sel[u]=0;
return false;
}
for(int i=root[u];i;i=edge[i].next){
int v=edge[i].to;
if(sel[v]==0){
if(!dfs(v)){
sel[u]=0;
return false;
}
}
}
return true;
}
void sync(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int main(){
sync();
cin>>n>>m;
while(m--){
int x,y,z,w;
cin>>x>>y>>z>>w;
add(x+(y)*n,z+(!w)*n);
add(z+(w)*n,x+(!y)*n);
}
for(int i=1;i<=2*n;i++){
if(!dfn[i])tarjan(i);
}
for(int i=1;i<=n;i++){
if(num[i]==num[i+n]){
printf("IMPOSSIBLE\n");
return 0;
}
}
for(int i=1;i<=n;i++){
if(sel[i]==0&&sel[i+n]==0){
if(!dfs(i)){
dfs(i+n);
}
}
}
printf("POSSIBLE\n");
for(int i=1;i<=n;i++){
printf("%d ",sel[i]>sel[i+n]);
}
putchar(10);
return 0;
}
|