What is 2-SAT you may ask
有很多集合,每个集合里有k个元素,要从中选择一个。除此以外,还有若干“选了A元素就必须选B”的限制,求一种可行的选择方案。
例题引入:poj3648
有一对新郎新娘准备婚礼,邀请了(n-1)对夫妇参加( n ≤ 30 n \leq 30 n≤30),其中有m个人有通奸关系(???),而且新郎新娘和别人,同性或异性都可能发生通奸关系(贵圈真乱…)。现在有一张长桌,有两边,一边坐着新娘一边坐着新郎,新娘不希望她对面有一对夫妇或者有通奸关系的人坐在一起,求一种排座位方案,输出坐新娘这边的人。
考虑先解决坐新郎这一边的人。假设存在通奸关系 ( A 1 , B 1 ) (A_1,B_1) (A1,B1), A 1 A_1 A1的伴侣是 A 2 A_2 A2, B 1 B_1 B1的伴侣是 B 2 B_2 B2,那么显然选了 A 1 A_1 A1就必须选 B 2 B_2 B2,选了 B 1 B_1 B1就必须选 A 2 A_2 A2。
How to deal with 2-SAT problem?
建图!边(x,y)表示选择x就必须选择y。
呃,对于这一题要解释一点,就是因为我们选择的是新郎这一边的人,所以我们要从新娘向新郎连一条边。这是由于2-SAT的建图特殊性质导致一个集合里的两个元素不会同时被选,也不会都不选(就无解啦),所以这样连边就保证了新郎要被选。
暴力法
暴力搜。每次选择了一个后,就暴力搜接下来必须选择的,然后把他们都选择,其伴侣都标记为不选择。如果不合法就换一种方式搜。
该方法实际应用的时候也不是很慢,而且如果求字典序最小方案就只能这么做了。
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>using namespace std;int read() {int q=0;char ch=' ';while(ch<'0'||ch>'9') ch=getchar();while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();return q;}#define RI register intconst int N=62,M=3605;int n,m,tot,top,bj[N],st[N],h[N],to[M],ne[M];void add(int x,int y) {to[++tot]=y,ne[tot]=h[x],h[x]=tot;}#define cp(x) (x<=n?x+n:x-n)int dfs(int x) {if(bj[x]==1) return 1;if(bj[x]==-1) return 0;bj[x]=1,bj[cp(x)]=-1,st[++top]=x;for(RI i=h[x];i;i=ne[i]) if(!dfs(to[i])) return 0;return 1;}void work() {for(RI i=1;i<=n;++i) {if(bj[i]) continue;top=0;if(!dfs(i)) {while(top) bj[st[top]]=bj[cp(st[top])]=0,--top;if(!dfs(cp(i))) {puts("bad luck");return;}}}for(RI i=1;i<n;++i)if(bj[i]==-1) printf("%dh ",i);else printf("%dw ",i);puts("");}int main(){int b1,b2;char c1,c2;while(~scanf("%d%d",&n,&m)&&(n+m)) {tot=0;for(RI i=1;i<=n*2;++i) h[i]=bj[i]=0;for(RI i=1;i<=m;++i) {scanf("%d%c%d%c",&b1,&c1,&b2,&c2);if(b1==0) b1=n; if(b2==0) b2=n;if(c1=='h'&&c2=='h') add(b1,b2+n),add(b2,b1+n);else if(c1=='h'&&c2=='w') add(b1,b2),add(b2+n,b1+n);else if(c1=='w'&&c2=='h') add(b1+n,b2+n),add(b2,b1);else add(b1+n,b2),add(b2+n,b1);}add(2*n,n),work();}return 0;}
乱搞法
方法原理会在“说明”里讲。
使用tarjan缩点,那么一个强连通分量里的点选一则必须选全部做一次检查,如果有一对夫妇在同一个强连通分量里,输出无解信息。用缩后的点建立新图,并把边反过来。这个新图称为图2,下列操作都在图2中进行。假如一对夫妇,丈夫在图2中的点A,妻子在点B,则标记B为A的对立节点,A为B的对立节点。拓扑排序。每次找到一个点,如果它上面没有打标记,打上选择标记,并把其对立点打上不选标记
好,那么这么做是否讲究了基本法呢?
首先,为什么要把边都反过来?
因为你是要去选点,而你选了一个点后,把这个“选择”的状态向下传递是非常麻烦的。
但是反边之后,选择标记就没必要传递了,不选标记变成了要传递的东西,这个又怎么传递呢?
我们是按照拓扑序在处理问题,也就是说,在图2中,如果一个不选的节点 x x x会走到一个没有打标记的节点 y y y,既然 y y y没打标记那么 y ′ y' y′也不会打标记,既然 x x x是不选标记那么在此之前已经处理了 x ′ x' x′。又由对称性, y y y的对立节点 y ′ y' y′会走到 x x x的对立节点 x ′ x' x′,那么 y ′ y' y′的拓扑序在 x x x之前,也就是 y y y这一对会被先打标记,然后再轮到 x x x这一对打标记,这就出现了矛盾。综上,没必要故意去传递标记,没打标记的节点就直接选就是。
然后,这样做凭什么保证一对夫妻不会同时不选?
其实这有很多情况,我就以一种情况为例说一说,其他的也差不多我懒就不说了。
假设这对可怜地被同时不选的夫妻为 ( x , x ′ ) (x,x') (x,x′),假设 y y y和 z z z都打上了不选标记,那么 y ′ y' y′和 z ′ z' z′应该被打上了选择标记,并已经被处理过。假设有 y − > x y -> x y−>x, z − > x ′ z -> x' z−>x′,这两条边,这样 x x x这对夫妻都不能被选了。由对称性, x ′ − > y ′ x' -> y' x′−>y′, x ′ − > z ′ x' -> z' x′−>z′,这两条边也存在,如图,显然 x x x和 x ′ x' x′没处理过之前,拓扑序处理是不会搞到 y ′ y' y′和 z ′ z' z′的。综上,这种情况不存在。
(下图中蓝色的点 Z Z Z应该为 Y ′ Y' Y′,手滑打错了抱歉)
那么这种算法就是讲究基本法的,代码实现如下:
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>using namespace std;int read() {int q=0;char ch=' ';while(ch<'0'||ch>'9') ch=getchar();while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();return q;}#define RI register intconst int N=62,M=3605;int n,m,tot,top,cnt,now;int dfn[N],low[N],st[N],col[N],ins[N],opp[N],du[N],bj[N];struct graph{int tot,h[N],to[M],ne[M];void add(int x,int y) {to[++tot]=y,ne[tot]=h[x],h[x]=tot;}}G1,G2;void tarjan(int x) {dfn[x]=low[x]=++now,st[++top]=x,ins[x]=1;for(RI i=G1.h[x];i;i=G1.ne[i])if(!dfn[G1.to[i]]) tarjan(G1.to[i]),low[x]=min(low[x],low[G1.to[i]]);else if(ins[G1.to[i]]) low[x]=min(low[x],dfn[G1.to[i]]);if(low[x]==dfn[x]) {++cnt;while(st[top]!=x) col[st[top]]=cnt,ins[st[top]]=0,--top;col[st[top]]=cnt,ins[st[top]]=0,--top;}}void topsort() {top=0;for(RI i=1;i<=cnt;++i) if(!du[i]) st[++top]=i;while(top) {int x=st[top];--top;if(!bj[x]) bj[x]=1,bj[opp[x]]=-1;for(RI i=G2.h[x];i;i=G2.ne[i]) {--du[G2.to[i]];if(!du[G2.to[i]]) st[++top]=G2.to[i];}}}void work() {for(RI i=1;i<=n*2;++i) if(!dfn[i]) tarjan(i);//缩点for(RI i=1;i<=n;++i) {//检查if(col[i]==col[i+n]) {puts("bad luck");return;}opp[col[i]]=col[i+n],opp[col[i+n]]=col[i];}for(RI x=1;x<=n*2;++x)//建新图for(RI i=G1.h[x];i;i=G1.ne[i])if(col[G1.to[i]]!=col[x])G2.add(col[G1.to[i]],col[x]),++du[col[x]];topsort();//拓扑排序处理for(RI i=1;i<n;++i)if(bj[col[i]]==-1) printf("%dh ",i);else printf("%dw ",i);puts("");}int main(){int b1,b2;char c1,c2;while(~scanf("%d%d",&n,&m)&&(n+m)) {G1.tot=G2.tot=cnt=now=top=0;for(RI i=1;i<=n*2;++i) G1.h[i]=G2.h[i]=dfn[i]=ins[i]=du[i]=bj[i]=0;for(RI i=1;i<=m;++i) {scanf("%d%c%d%c",&b1,&c1,&b2,&c2);if(b1==0) b1=n; if(b2==0) b2=n;if(c1=='h'&&c2=='h') G1.add(b1,b2+n),G1.add(b2,b1+n);else if(c1=='h'&&c2=='w') G1.add(b1,b2),G1.add(b2+n,b1+n);else if(c1=='w'&&c2=='h') G1.add(b1+n,b2+n),G1.add(b2,b1);else G1.add(b1+n,b2),G1.add(b2+n,b1);}G1.add(2*n,n),work();}return 0;}
哦,原来2-SAT是这么一回事!
update
xzy跟我说其实没必要再做一遍toposort的……
因为tarjan完了后你缩出来的点的顺序就是缩点后图的拓扑序的反序……
以下是洛谷P4782的代码:
#include<bits/stdc++.h>using namespace std;#define RI register intint read() {int q=0;char ch=' ';while(ch<'0'||ch>'9') ch=getchar();while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();return q;}const int N=2000005;int n,m,tot,top,tim,cnt;int h[N],ne[N],to[N],dfn[N],low[N],st[N],ins[N],col[N],opp[N],bj[N];void add(int x,int y) {to[++tot]=y,ne[tot]=h[x],h[x]=tot;}void tarjan(int x) {dfn[x]=low[x]=++tim,ins[x]=1,st[++top]=x;for(RI i=h[x];i;i=ne[i])if(!dfn[to[i]]) tarjan(to[i]),low[x]=min(low[x],low[to[i]]);else if(ins[to[i]]) low[x]=min(low[x],dfn[to[i]]);if(dfn[x]==low[x]) {++cnt;while(st[top]!=x) col[st[top]]=cnt,ins[st[top]]=0,--top;col[st[top]]=cnt,ins[st[top]]=0,--top;}}void work() {for(RI i=2;i<=((n<<1)|1);++i) if(!dfn[i]) tarjan(i);for(RI i=1;i<=n;++i) {if(col[i<<1]==col[(i<<1)|1]) {puts("IMPOSSIBLE");return;}opp[col[i<<1]]=col[(i<<1)|1];opp[col[(i<<1)|1]]=col[i<<1];}for(RI i=1;i<=cnt;++i)if(!bj[i]) bj[i]=1,bj[opp[i]]=-1;puts("POSSIBLE");for(RI i=1;i<=n;++i) printf(bj[col[i<<1]]==1?"0 ":"1 ");puts("");}int main(){n=read(),m=read();for(RI i=1;i<=m;++i) {int x1=read(),a1=read(),x2=read(),a2=read();add((x1<<1)|(a1^1),(x2<<1)|a2);add((x2<<1)|(a2^1),(x1<<1)|a1);}work();return 0;}
如果觉得《原来2-SAT是这么一回事》对你有帮助,请点赞、收藏,并留下你的观点哦!