很开心,图论的知识也是积少成多,回首往昔,我对图论的算法仅限于最短路算法($\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; }
|