juju527's blog

因为失去，所以明白

2-SAT

发布于 2020-06-06 | 分类于 2-SAT 、 学习笔记 | 14分钟 | 2879字数 | 浏览量：

2-SAT模板部分

强连通分量

upd on 11.6

拆点与建边

将题目转化成一个图论问题
考虑将每一个变量拆成两个点，分别表示该位选0或1
具体实现可以用ii号点表示第ii位选0，i+ni+n号点表示第ii位选1
ii与i+ni+n是一对相逆的命题
下述用“满足pp”来叙述满足p点选择的意义
由于我们需要满足的操作形式为(XiX_i为aa或XjX_j为bb)
“或”这个操作我们并不会处理，我们考虑将其转化为两个条件的“且”
(XiX_i为¬a\neg a时，XjX_j一定为bb)且(XjX_j为¬b\neg b时，XiX_i一定为aa)
容易看出这两个条件的“与”与原要求条件等价
我们定义图中一条边(u,v)(u,v)的意义为满足uu时,vv一定满足
那么我们根据上述分析可以建边

(¬a,b)(\neg a,b)
(¬b,a)(\neg b,a)

判断无解与构造方案

考虑一条边(u,v)(u,v)的含义为选u必选v，那么u能走到v，即选u必选v
无解自然是 u,¬uu,\neg u 互相可达，即其在同一连通块中
tarjan即可判断

至于构造一组合法解
由于u能到v表示选u必选v，我们需要判断 uu 和¬u\neg u 之间有没有到达关系
我们考虑tarjan的过程得到的强连通分量dfs序
其实质为反拓扑序
考虑拓扑序的性质，若u能走到v，则u的拓扑序一定在v之前
对于一个0/1变量u的取值我们只要钦定 uu 和 ¬u\neg u 点中拓扑序较大的那个即可

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5,maxm=1e6+5;
struct Edge{
	int to,nxt;
}e[2*maxm];
int cnt;
int head[maxn<<1];
int read(){
    int x=0,y=1;
    char ch=getchar();
    while(ch<48||ch>57){if(ch==45)y=-1;ch=getchar();}
    while(ch>=48&&ch<=57)x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*y;
}
void add(int u,int v){
	e[cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt++;
	return ;
}
int dfsnum;
int dfn[maxn<<1],low[maxn<<1];
bool vis[maxn<<1];
int num;
int b[maxn<<1];
stack<int>s;
void tarjan(int x){
	dfn[x]=low[x]=++dfsnum;
	vis[x]=1;
	s.push(x);
	for(int i=head[x];i!=-1;i=e[i].nxt){
		int tmp=e[i].to;
		if(!dfn[tmp]){
			tarjan(tmp);
			low[x]=min(low[x],low[tmp]);
		}
		else if(vis[tmp])
			low[x]=min(low[x],dfn[tmp]);
	}
	if(dfn[x]==low[x]){
		num++;
		while(s.top()^x){
			b[s.top()]=num;
			vis[s.top()]=0;
			s.pop();
		}
		b[s.top()]=num;
		vis[s.top()]=0;
		s.pop();
	}
	return ;
}
int main(){
//    freopen("P4782.in","r",stdin);
//    freopen("P4782.out","w",stdout);
   	int n,m;
	n=read();m=read();
	memset(head,-1,sizeof(head));
	for(int i=1;i<=m;i++){
		int x,a,y,b;
		x=read();a=read();y=read();b=read();
		if(a&&b){
			add(x,y+n);
			add(y,x+n);
		}
		else if(a){
			add(x,y);
			add(y+n,x+n);
		}
		else if(b){
			add(x+n,y+n);
			add(y,x);
		}
		else{
			add(x+n,y);
			add(y+n,x);
		}
	}
	for(int i=1;i<=2*n;i++)
		if(!dfn[i])
			tarjan(i);
	for(int i=1;i<=n;i++)
		if(b[i]==b[i+n]){
			printf("IMPOSSIBLE\n");
			return 0;
		}
	printf("POSSIBLE\n");
	for(int i=1;i<=n;i++)
		printf("%d ",b[i]>b[i+n]);
    return 0;
}

纯dfs写2-SAT

upd on 11.6 这个做法被洛谷一个老哥叉掉了，复杂度可能达到 O(n2)O(n^2)，之前学的时候理解不深，非常抱歉

看到各位大佬都用的是强连通分量的算法，无论是tarjan还是kosaraju
这里给出一个不需要强连通分量的做法

拆点与建边

将题目转化成一个图论问题
考虑将每一个变量拆成两个点，分别表示该位选0或1
具体实现可以用ii号点表示第ii位选0，i+ni+n号点表示第ii位选1
ii与i+ni+n是一对相逆的命题
下述用“满足pp”来叙述满足pp点选择的意义
由于我们需要满足的操作形式为(XiX_i为aa或XjX_j为bb)
“或”这个操作我们并不会处理，我们考虑将其转化为两个条件的“且”
(XiX_i为¬a\neg a时，XjX_j一定为bb)且(XjX_j为¬b\neg b时，XiX_i一定为aa)
容易看出这两个条件的“与”与原要求条件等价
我们定义图中一条边(u,v)(u,v)的意义为满足uu时,vv一定满足
那么我们根据上述分析可以建边

(¬a,b)(\neg a,b)
(¬b,a)(\neg b,a)

实现

建好了图，但是图有什么用呢
由于我们需要构造一组解，我们考虑枚举每一个元素选0/10/1
从枚举点uu出发搜索
考虑到我们定义的边的意义，由于我们钦定uu满足
故所有与uu相连的点都满足
容易推得uu能走到的点都应满足
若此时uu能走到的集合或之前枚举到能走到的集合中包括了某对点x,x+nx,x+n,那么该方案一定无解
原因是两个相逆的命题无法同时成立
这个应该很好理解
此时原问题一定无解吗？显然不是，我们还应考虑¬u\neg u
当¬u\neg u搜出来也无解时原问题无解
是否还有其它无解情况？
再次考虑边的意义，一条有向边(u,v)(u,v),只有uu的决策能影响到vv,而无论vv如何都无法影响uu
这是由我们转化的两个条件所决定的，前者是后者的条件

(XiX_i为¬a\neg a时，XjX_j一定为bb)且(XjX_j为¬b\neg b时，XiX_i一定为aa)
而我们对于uu考虑了它所有能到达（影响）的点，不存在我们没考虑到的情况

优缺点分析

相比强连通分量的做法，该做法的构造难度较小
做法直接枚举0/10/1当然难度小
复杂度也是线性

说实话前面讲了一大堆奇奇怪怪的东西也许都还有问题
欢迎来卡

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000005,maxm=1000005;
struct Edge{
	int to,nxt;
}e[2*maxm];
int cnt;
int head[2*maxn];
int n,m;
bool flag[2*maxn];
int tp=0;
int s[2*maxn];
int ans[maxn];
int read(){
	int x=0,y=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*y;
}
void add(int u,int v){
	e[cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt++;
	return ;
}
bool dfs(int x){
	if(flag[x>n?x-n:x+n])return 0;
	if(flag[x])return 1;
	flag[x]=1;
	s[++tp]=x;
	for(int i=head[x];i!=-1;i=e[i].nxt){
		int tmp=e[i].to;
		if(!dfs(tmp))return 0;
	}
	return 1;
}
int main(){
	n=read();m=read();
	memset(head,-1,sizeof(head));
	for(int i=1;i<=m;i++){
		int u,a,v,b;
		u=read();a=read();v=read();b=read();
		if(a==0&&b==0){
			add(u+n,v);
			add(v+n,u);
		}
		else if(a==0&&b==1){
			add(u+n,v+n);
			add(v,u);
		}
		else if(a==1&&b==0){
			add(u,v);
			add(v+n,u+n);
		}
		else{
			add(u,v+n);
			add(v,u+n);
		}
	}
	for(int i=1;i<=n;i++){
		tp=0;
		ans[i]=0;
		if(!dfs(i)){
			while(tp)flag[s[tp--]]=0;
			ans[i]=1;
			if(!dfs(i+n)){
				printf("IMPOSSIBLE\n");
				return 0;
			}
		}
	}
	printf("POSSIBLE\n");
	for(int i=1;i<=n;i++)
		printf("%d ",ans[i]); 
	return 0;
}

练习题部分

upd on 11.6
从模板的学习我们可以发现2-SAT的核心在于建图，这也是图论问题的普遍核心
发现题目中某元素的两种取值与两两间的限制就能将其转换成我们熟悉的2-SAT问题
当然，作为图论问题也会有一些更加复杂的拆点技巧，建边优化

[POI2011]KON-Conspiracy

显然，本题的两种取值即后勤者与同谋者两种
若一个人要是后勤者，所有跟他不熟的人应均为同谋者
若一个人要是同谋者，所有跟他熟悉的人应均为后勤者
边数 O(n2)O(n^2) ，我们能够承受

建出图后无解就容易判断了
考虑如何计算方案
构造一组合法解后看能否该边某人的阵营是我们的核心思路
容易发现，同阵营中不能同时将两人以上放入对方阵营
我们需要讨论的其实很少（这一个发现至关重要）
考虑把某个后勤者改为同谋者的合法条件
他要和同谋者阵营中的所有人均不认识，我们可以把他放入同谋者阵营
或者与同谋者阵营中唯一一人认识，且该人认识后勤者阵营所有人，我们可以把两人交换阵营
同谋改后勤类似
可以记录一个值 sumisum_i 表示i点在对方阵营的不满足条件点数
我们只要处理三种情况

  1. 0点的直接改变
  2. 0，0点之间的交换
  3. 0，1点之间的交换
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
using namespace std;
#define R register
const int maxn=5005;
struct Edge{
    short to;
    int nxt;
}e[2*maxn*maxn];
int cnt;
int head[2*maxn];
bool know[maxn][maxn];
int tot;
short id1[maxn],id2[maxn];
bool c[maxn];
short sum[maxn];
short to[maxn];
int read(){
    int x=0,y=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*y;
}
void add(int u,int v){
//    cout<<"*"<<u<<" "<<v<<endl;
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt++;
    return ;
}
int dfsnum;
int dfn[2*maxn],low[2*maxn];
bool vis[2*maxn];
int num;
int b[2*maxn];
stack<int>s;
inline void tarjan(int x){
    dfn[x]=low[x]=++dfsnum;
    vis[x]=1;
    s.push(x);
    for(int i=head[x];i!=-1;i=e[i].nxt){
        int tmp=e[i].to;
        if(!dfn[tmp]){
            tarjan(tmp);
            low[x]=min(low[x],low[tmp]);
        }
        else if(vis[tmp])
            low[x]=min(low[x],dfn[tmp]);
    }
    if(dfn[x]==low[x]){
        num++;
        while(s.top()!=x){
            b[s.top()]=num;
            vis[s.top()]=0;
            s.pop();
        }
        b[s.top()]=num;
        vis[s.top()]=0;
        s.pop();
    }
    return ;
}
int main(){
    int n;
    n=read();
    memset(head,-1,sizeof(head));
    for(R int i=1;i<=n;i++){
        int k;
        k=read();
        id1[i]=++tot;id2[i]=++tot;
        for(R int j=1;j<=k;j++)know[i][read()]=1;
    }
    for(R int i=1;i<=n;i++){
        for(R int j=i+1;j<=n;j++){
            if(know[i][j]){
                add(id1[i],id2[j]);
                add(id1[j],id2[i]);
            }
            else{
                add(id2[i],id1[j]);
                add(id2[j],id1[i]);
            }
        }
    }
    for(int i=1;i<=tot;i++)
        if(!dfn[i])
            tarjan(i);
    for(int i=1;i<=n;i++)
        if(b[id1[i]]==b[id2[i]]){
            puts("0");
            return 0;
        }
    int S=0;
    for(int i=1;i<=n;i++){c[i]=(b[id1[i]]>b[id2[i]]);S+=c[i];}
    for(R int i=1;i<=n;i++){
        for(R int j=1;j<=n;j++){
            if(c[j]==c[i])continue;
            if(c[i]){if(know[i][j])sum[i]++,to[i]=j;}
            else{if(!know[i][j])sum[i]++,to[i]=j;}
        }
    }
    int ans=(S<n&&S>0),s0=0,s1=0;
    for(R int i=1;i<=n;i++){
        if(sum[i]==1)if(sum[to[i]]==0)ans++;
        if(sum[i]==0){
            if(c[i]){
                if(S>1)ans++;
                s1++;
            }
            else{
                if(n-S>1)ans++;
                s0++;
            }
        }
    }
    printf("%d\n",ans+((S>=1&&n-S>=1)?s0*s1:0));
    return 0;
}

其他习题

[NOI2017]游戏 通过简单操作将少量3取值点变为2取值
[PA2010]Riddle 优化建边2-SAT
Manhattan 对2-SAT建边理解更加透彻

# 2-SAT # 学习笔记
HNOI2020游记 上一篇
【题解】 P4585 [FJOI2015]火星商店问题 下一篇
0%