2-sat学习笔记
2-sat
题目：[模板]2-SAT 问题
题目描述:
有n个布尔变量，另有m个需要满足的条件，每个条件的形式都是“
为true/false或
为true/false”。比如“
为真或
为假”、“
为假或
为假”。2-SAT 问题的目标是给每个变量赋值使得所有条件得到满足。
题解：
0表示不选，1表示选
1.a=0 , a->a'
2.a=1 , a'->a
3.a=1那么b=1 , a->b b'->a'(隐藏b=0那么a=0)
4.a=0那么b=0 , a'->b' b->a(隐藏b=1那么a=1)
5.a=1那么b=0 , a->b' b->a'(隐藏b=1那么a=0)
6.a=0那么b=1 , a'->b b'->a(隐藏b=0那么a=1)
7.a=0并且b=0 a=0并且b=1 a=1并且b=0 a=1并且b=1 参考3-6,进行合并
8.a^b=0 a^b!=0 参考3-6,进行合并
如果col[a]==col[a'],那么无解。
关于求一组解，由于我们知道tarjan的dfn序其实就是拓扑的反序，所以当col[a]<col[a']时，a=1。
代码：
#include<bits/stdc++.h>
using namespace std;
#define next Next
#define last Last
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}*/
#define gc getchar
inline int read()
{
int ret=0,f=0;char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){ret=ret*10+c-48;c=gc();}
if(f)return -ret;return ret;
}
const int N=2e6+5;
int n,m,top,deep,tot,color;
int dfn[N],low[N],zhan[N],col[N],head[N];
bool vis[N];
struct node{
int too,next;
}edge[N];
void add(int a,int b)
{
edge[++top].too=b;edge[top].next=head[a];head[a]=top;
}
void tarjan(int u)
{
deep++;dfn[u]=low[u]=deep;
vis[u]=true;zhan[++tot]=u;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].too;
if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}
else if(vis[v])low[u]=min(low[u],low[v]);
}
if(dfn[u]==low[u])
{
color++;vis[u]=false;col[u]=color;
while(zhan[tot]!=u)
{
vis[zhan[tot]]=false;
col[zhan[tot]]=color;
tot--;
}
tot--;
}
}
bool TWO_SAT()
{
for(int i=1;i<=2*n;i++)
if(!dfn[i])tarjan(i);
for(int i=1;i<=n;i++)
if(col[i]==col[i+n])return false;
return true;
}
signed main()
{
n=read();m=read();
for(int i=1;i<=m;i++)
{
int a=read(),x=read(),b=read(),y=read();
if(x==0)
{
if(y==0)//a=1那么b=0(b=1那么a=0)
{
add(a,b+n);
add(b,a+n);
}
else{//a=1那么b=1(b=0那么a=0)
add(a,b);
add(b+n,a+n);
}
}
else{
if(y==0)//a=0那么b=0(b=1那么a=1)
{
add(a+n,b+n);
add(b,a);
}
else{//a=0那么b=1(b=0那么a=1)
add(a+n,b);
add(b+n,a);
}
}
}
if(TWO_SAT())
{
puts("POSSIBLE");
for(int i=1;i<=n;i++)
printf("%d ",col[i]<col[i+n]);
}
else printf("IMPOSSIBLE");
return 0;
} 题目：[JSOI2010]满汉全席
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int T,n,m,x,y,xx,yy,deep,color,cnt,tot,top;
int dfn[N],low[N],head[N],col[N],zhan[N];
char s1[50],s2[50];
struct node{
int too,next;
}edge[N];
bool vis[N];
void add(int a,int b)
{
edge[++top].too=b;edge[top].next=head[a];head[a]=top;
}
void tarjan(int u)
{
deep++;
dfn[u]=low[u]=deep;
zhan[++tot]=u;vis[u]=true;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].too;
if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}
else if(vis[v])low[u]=min(low[u],low[v]);
}
if(dfn[u]==low[u])
{
color++;col[u]=color;vis[u]=false;
while(zhan[tot]!=u)
{
col[zhan[tot]]=color;
vis[zhan[tot]]=false;
tot--;
}
tot--;
}
}
bool TWO_SAT()
{
for(int i=1;i<=2*n;i++)
if(!dfn[i])tarjan(i);
for(int i=1;i<=n;i++)
if(col[i]==col[i+n])return false;
return true;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
cnt=tot=0;
for(int i=1;i<=2*n;i++)
head[i]=low[i]=dfn[i]=col[i]=vis[i]=0;
for(int i=1;i<=m;++i)
{
scanf("%s%s",s1,s2);
int u=0,v=0,k;
k=1;while(s1[k]>='0'&&s1[k]<='9')u=u*10+s1[k++]-'0';
k=1;while(s2[k]>='0'&&s2[k]<='9')v=v*10+s2[k++]-'0';
if(s1[0]=='m')
{
if(s2[0]=='h')add(u+n,v+n),add(v,u);
else if(s2[0]=='m')add(u+n,v),add(v+n,u);
}
else if(s1[0]=='h')
{
if(s2[0]=='h')add(u,v+n),add(v,u+n);
else if(s2[0]=='m')add(u,v),add(v+n,u+n);
}
}
if(TWO_SAT())printf("GOOD\n");
else printf("BAD\n");
}
} 题目：[NOI2017]游戏
题解：
a,b,c三种赛道都是普通2-set。但x赛道不是。
怎么办？由于x赛道数量少，我们暴力枚举是变成a或b即可。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,num,deep,color,tot,top;
int dfn[N],low[N],head[N],col[N],zhan[N],b[N],pos[N];
char s[N];
struct node{
int too,next;
}edge[N];
struct node2{
int x,a,y,b;
}a[N];
bool vis[N];
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc()
{
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}*/
#define gc getchar
inline int read()
{
int ret=0,f=0;
char c=gc();
while(!isdigit(c))
{
if(c=='-')f=1;
c=gc();
}
while(isdigit(c))
{
ret=ret*10+c-48;
c=gc();
}
if(f)return -ret;
return ret;
}
int get(int x,int c)
{
if(b[x]==1)return c==2?x:x+n;
if(b[x]==2||b[x]==3)return c==1?x:x+n;
}
int nxt(int x)
{
return x>n?x-n:x+n;
}
void clean()
{
top=color=deep=tot=0;
memset(head,0,sizeof(head));
memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn));
memset(vis,0,sizeof(vis));
memset(col,0,sizeof(col));
}
void add(int a,int b)
{
edge[++top].too=b;edge[top].next=head[a];head[a]=top;
}
void build()
{
for(int i=1;i<=m;i++)
{
int x=a[i].x,y=a[i].y;
if(b[x]==a[i].a)continue;
int u=get(x,a[i].a),v=get(y,a[i].b);
if(b[y]==a[i].b)
{
add(u,nxt(u));
continue;
}
add(u,v);//选a，一定要选b
add(nxt(v),nxt(u));//不选b，一定不选a
}
}
void tarjan(int u)
{
deep++;
dfn[u]=low[u]=deep;
zhan[++tot]=u;vis[u]=true;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].too;
if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}
else if(vis[v])low[u]=min(low[u],low[v]);
}
if(dfn[u]==low[u])
{
color++;col[u]=color;vis[u]=false;
while(zhan[tot]!=u)
{
col[zhan[tot]]=color;
vis[zhan[tot]]=false;
tot--;
}
tot--;
}
}
bool TWO_SAT()
{
for(int i=1;i<=2*n;i++)
if(!dfn[i])tarjan(i);
for(int i=1;i<=n;i++)
if(col[i]==col[i+n])return false;
return true;
}
void dfs(int x)
{
if(x>num)
{
clean();
build();
if(TWO_SAT())
{
for(int i=1;i<=n;i++)
{
if(col[i]<col[nxt(i)])putchar(b[i]==1?'B':'A');
else putchar(b[i]==3?'B':'C');
}
exit(0);
}
return;
}
b[pos[x]]=1;
dfs(x+1);
b[pos[x]]=2;
dfs(x+1);
}
int main()
{
n=read();read();
cin>>s+1;
for(int i=1;i<=n;i++)
{
if(s[i]=='x')pos[++num]=i;
b[i]=s[i]-'a'+1;
}
m=read();
char c1,c2;
for(int i=1;i<=m;i++)
{
cin>>a[i].x>>c1>>a[i].y>>c2;
a[i].a=c1-'A'+1;
a[i].b=c2-'A'+1;
}
dfs(1);
puts("-1");
return 0;
} 题目：National Property
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,deep,color,tot,top,a[N],b[N];
int dfn[N],low[N],head[N],col[N],zhan[N];
struct node{
int too,next;
}edge[N];
bool vis[N];
void add(int a,int b)
{
edge[++top].too=b;edge[top].next=head[a];head[a]=top;
}
void tarjan(int u)
{
deep++;
dfn[u]=low[u]=deep;
zhan[++tot]=u;vis[u]=true;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].too;
if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}
else if(vis[v])low[u]=min(low[u],low[v]);
}
if(dfn[u]==low[u])
{
color++;col[u]=color;vis[u]=false;
while(zhan[tot]!=u)
{
col[zhan[tot]]=color;
vis[zhan[tot]]=false;
tot--;
}
tot--;
}
}
bool TWO_SAT()
{
for(int i=1;i<=2*n;i++)
if(!dfn[i])tarjan(i);
for(int i=1;i<=n;i++)
if(col[i]==col[i+n])return false;
return true;
}
int main()
{
scanf("%d%d",&m,&n);
for(int j=1;j<=m;j++)
{
scanf("%d",&a[0]);
for(int i=1;i<=a[0];i++)scanf("%d",&a[i]);
if(j>1)
{
for(int i=1;i<=min(a[0],b[0]);i++)
{
if(b[i]<a[i])
{
add(a[i],b[i]);
add(b[i]+n,a[i]+n);
break;
}
else if(a[i]<b[i])
{
add(b[i]+n,b[i]);
add(a[i],a[i]+n);
break;
}
if(i==min(a[0],b[0])&&b[0]>a[0])
{
puts("No");
return 0;
}
}
}
for(int i=0;i<=a[0];i++)b[i]=a[i];
}
if(TWO_SAT())
{
puts("Yes");
int ans=0;
for(int i=1;i<=n;i++)
if(col[i]<col[i+n])ans++;
cout<<ans<<endl;
for(int i=1;i<=n;i++)
if(col[i]<col[i+n])printf("%d ",i);
}
else printf("No");
return 0;
} xuxuxuxuxu 文章被收录于专栏
信息学竞赛
投递作业帮等公司10个岗位
