• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

2-sat 学习笔记

开发技术 开发技术 5小时前 2次浏览

1.前言:

这个蒟蒻自己都还没学明白,所以讲的不清楚一定要快评论下来,然后这样蒟蒻思考了给大佬一点启发。

2.正文:

(2-sat) 是什么呢?

其实就是这样的,(2-sat) 问题是形如: 有 (n) 个人,每个人可以是男的和女的,要满足他们之间的一类关系,比如 (i)(j) 中一个是男的,一个是女的。或者都是男的,或者都是女的。让你对他们安排性别满足条件。

用正式一点的话就是,有 (n) 个布尔变量,每个变量可以为 (0) 或者 (1) 。让你去安排每个变量是 (0) 还是 (1) ,去满足约束条件。

当然有 (2-sat) 就有 (k-sat) 等,但是目前 (k > 2) 是多项式时间不可解的问题。

我们谈谈 (2-sat) 的问题是怎么解决的。

这里我们先引入一道例题

我们发现这道题里面,是一个很裸的 (2-sat) ,我们思考每个变量之间的关系。

我们首先发现的是每一个点,只有 (2) 个变量取值,我们考虑把每个变量 (i) 拆成两个点 (i)(i+n) 。表示两个点是 (text{true}) 还是 (text{false})

2-sat 学习笔记

然后我们去考虑对于每一条限制怎么做。

如果有 (a) & (b=0)

这个表明了 (a)(b) 里面一定有一个是 (0)

那么我们要在 (a)(true) 里 连边向 (b)(false) 。并且将 (b)(true) 连向 (a)(false)

2-sat 学习笔记

这样可以保证的是无论这两个的取值是怎样,反正最终会有一个走向 (false) 。所以这个建边是没问题的,这里应该没问题。

但是,有问题就是我们为什么不能去,从 (b)(false) 连向 (a)(true)

这么乍一看也没什么问题啊?

但是这样不行的,因为如果 (b)(false) 其实 (a)(true) 还是 (false) 都是没问题的。而这么连边就是不明确的关系,让人认为,选了(b)(false)(a) 就只能为 (true) 了,所以不行。

那么建图是怎样的呢?大概描述一下流程的话。就是:

  • (a,b) 不能同时选,那么选了 (a) 就要选 (b+n) ,选了 (b) 就要选 (a+n)(arightarrow b+n)(b rightarrow a+n)
  • (a,b) 必须同时选,那么选了 (a) 就要选 (b) ,选了 (b) 就要选 (a) 。则 (arightarrow b)(b rightarrow a)
  • (a,b) 中至少选一个,那么选了 (a) 就要选 (b+n) ,选 (b) 就要选 (a+n) ,选了 (a+n) 就要选 (b) ,选了 (b+n) 就要选 (a) 。则 (arightarrow b+n)(b rightarrow a+n)(a+n rightarrow b)(b+n rightarrow a)
  • (a,b)(a) 必须选,那么让 (a+n rightarrow a)

然后就可以了完成建图过程,但是我们还需要知道是否存在分派方案和怎么分配。

怎么去判断是否有解,在 (text{hl666}) 神仙的博客里学到了两种方法。

第一种:(text{DFS})
  1. 对于每个不确定的变量 (a_i) ,令其为0,然后沿边访问相连的点。
  2. 检查是否会导致任意一个 (b)(b+n) 都被选中,如果不会那么撤销让 (a_i=0)
  3. 否则让 (a_i=1) 重复 (2) 操作。
  4. 继续考虑不确定的限制

复杂度为 (n^2+nm) ,可以用 (bitset) 优化传递闭包后进行 (dfrac{n^3}{w}) 的预处理做到 (n+m) 的 DFS 。

这样做可以保证求解出的答案字典序最小。

第二种:(text{Tarjan})

无解的情况其实就是某一变量的 (false) 走到 (true) 而从 (true) 也能走到 (false) 也就是一个变量的取值在同一强连通分量内就无解。

而且分析一下,你还可以知道,在同一强连通分量内的变量取值相同。

怎么去求解取值呢?

我们要选的其实就是在图中被边指着的变量值,这样才可以保证不会产生矛盾。

那么在拓扑序上就是我们要选择拓扑序上较大的值。

因为在有向图中拓扑排序后,被指向的点的拓扑序大于指向它的点。

但是其实在求解 (text{Tarjan}) 时已经求解除了拓扑序,只不过时反向的,可以思考 $text{Tarjan} $ 的过程理解。

然后取两个取值中强连通分量的编号较小的所对应的值就可以了。

时间复杂度为 (n+m)

下面给出例题代码的参考实现:


#include<bits/stdc++.h>
using namespace std;
#define MAXN 900
struct ios_in{
 inline char gc(){
  static char buf[MAXN],*l,*r;
  return (l==r)&&(r=(l=buf)+fread(buf,1,MAXN,stdin),l==r)?EOF:*l++;
 }
 template <typename _Tp>
 inline ios_in&operator>>(_Tp&x){
  static char ch,sgn;
  for(sgn=0,ch=gc();!isdigit(ch);ch=gc()) {
   if(!~ch) return *this;
   sgn|=ch=='-';
  }
  for(x=0;isdigit(ch);ch=gc()) x=(x<<1)+(x<<3)+(ch^'0');
   sgn&&(x=-x);
   return *this;
 }
}Cin;
const int N = 3e6;
int n,m,x[N];
int dfn[N],low[N],cnt,nex[N],first[N],v[N],num;
int ins[N],tp,sc,scc[N],sz[N],s[N];
//scc[i]表示i所在scc的编号
void add(int from,int to){nex[++num]=first[from];first[from]=num;v[num]=to;	}
void tarjan(int u){
 low[u]=dfn[u]=++cnt;s[++tp]=u;ins[u]=1;
 for(int i=first[u];i;i=nex[i]){
  int to=v[i];
  if(!dfn[to]){
   tarjan(to);
   low[u]=min(low[u],low[to]);	
  }
  else if(ins[to]){
   low[u]=min(low[u],dfn[to]);	
  }	
 }
 if(dfn[u]==low[u]){
  ++sc;
  while(s[tp]!=u){
   scc[s[tp]]=sc;
   sz[sc]++;
   ins[s[tp]]=0;
   --tp;	
  }
  scc[s[tp]]=sc;
  sz[sc]++;
  ins[s[tp]]=0;
  --tp;	
 }	
} 
signed main(){
 Cin>>n>>m;
 for(int i=1;i<=m;i++){
  int a,b,c,d;
  Cin>>a>>c>>b>>d;
  if(c&&d){
   add(a,b+n);
   add(b,a+n);	
  }
  if(!c&&!d){
   add(a+n,b);
   add(b+n,a);	
  }
  if(c&&!d){
   add(a,b);
   add(b+n,a+n);	
  }
  if(!c&&d){
   add(a+n,b+n);
   add(b,a);	
  }	
 }
 for(int i=1;i<=2*n;i++)
  if(!dfn[i]) tarjan(i);	
 
 for(int i=1;i<=n;i++)
  if(scc[i]==scc[i+n]){printf("IMPOSSIBLE");return 0;}	
 
 printf("POSSIBLEn");
 for(int i=1;i<=n;i++){
  if(scc[i]>scc[i+n]){//强连通分量小,拓扑序大,答案优秀 
   printf("1 "); 	
  }
  else printf("0 ");	
 }
 return 0;	
}

下面有思路一样的双倍经验。

不过要注意对字符串后面数字的处理要处理完,它不止一位。

到此就介绍完了 (2-sat) 算法,下面会更新一下例题辅助理解,期待!

3.参考资料:

2-SAT超入门讲解

2-SAT总结

2-sat研究


程序员灯塔
转载请注明原文链接:2-sat 学习笔记
喜欢 (0)