Tarjan在图论中的应用（三）—

前言

\(2-SAT\)的解法不止一种（例如暴搜？），但最高效的应该还是\(Tarjan\)。

说来其实我早就写过用\(Tarjan\)求解\(2-SAT\)的题目了（就是这道题：【2019.8.14 慈溪模拟赛 T2】黑心老板（gamble）），这篇博客本来已经石沉大海，打算坑掉了的，但由于在\(CSP-S\)前复习板子时忘记了这道题写法，结果板子题都挂了好几次，为了加深印象，为了自我惩罚，来补博客了。

基本模型

什么是\(2-SAT\)？

考虑有\(n\)个物品，每个物品有\(0\)和\(1\)两种取值。给出一些诸如第\(i\)个物品是\(0/1\)或第\(j\)个物品是\(0/1\)的限制，如：

第\(1\)个物品是\(0\)或第\(2\)个物品是\(1\)。
第\(1\)个物品是\(1\)或第\(3\)个物品是\(1\)。
......

而\(2-SAT\)，就是求出一个满足所有条件的可行解，或是判断无解。

建图

既然提到要用\(Tarjan\)了，那么首先我们需要把这个问题转移到图上。

我们把每个物品看作两个点，分别表示这个物品取\(0\)和取\(1\)。

由于题目中给出的限制不是很明确，所以我们要先将它进行转化。

例如，若题目中给出第\(i\)个物品是\(x\)或第\(j\)个物品是\(y\)。

那么如果第\(i\)个物品是\(!x\)，第\(j\)个物品就必须是\(y\)。反之，如果第\(j\)个物品是\(!y\)，第\(i\)个物品就必须是\(x\)。

即，将\((i,!x)\)向\((j,y)\)连边，\((j,!y)\) 向\((i,x)\)连边。

求解

首先，我们考虑，如何判断已知的一组解\(ans\)的合法性。

不难发现，若能从\((i,ans_i)\)走到\((i,!ans_i)\)，就说明这组解是不合法的。

这无疑带给我们一些启发。

如果存在\((i,0)\)与\((i,1)\)能互相到达，那么就是无解的。否则一定有解。

结合强连通分量的概念，即若\((i,0)\)与\((i,1)\)在同一个强连通分量中，就无解。

然后我们要考虑如何找到一组可行解。

如果\((i,0)\)所在的连通块能到达\((i,1)\)，\(i\)就一定要选\(1\)，反之亦然。

而能到达，一个必要条件就是缩点后拓扑序较小。

而要比较拓扑序，实际上也可以直接比较所在连通块缩点后的编号，根据\(Tarjan\)的原理，显然编号越小拓扑序越大。

因此我们只要选择编号较小的方案即可。

代码

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define N 1000000

#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)

#define Gmin(x,y) (x>(y)&&(x=(y)))

using namespace std;

int n,m,ee,lnk[2*N+5];struct edge {int to,nxt;}e[2*N+5];

class FastIO

{

	private:

		#define FS 100000

		#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)

		#define pc(c) (C==E&&(clear(),0),*C++=c)

		#define tn (x<<3)+(x<<1)

		#define D isdigit(c=tc())

		int T;char c,*A,*B,*C,*E,FI[FS],FO[FS],S[FS];

	public:

		I FastIO() {A=B=FI,C=FO,E=FO+FS;}

		Tp I void read(Ty& x) {x=0;W(!D);W(x=tn+(c&15),D);}

		Tp I void write(Ty x) {W(S[++T]=x%10+48,x/=10);W(T) pc(S[T--]);}

		Tp I void write(Con Ty& x,Con char& y) {write(x),pc(y);}

		I void clear() {fwrite(FO,1,C-FO,stdout),C=FO;}

}F;

namespace Tarjan//Tarjan缩点

{

	int d,T,cnt,dfn[2*N+5],low[2*N+5],vis[2*N+5],S[2*N+5],col[2*N+5];

	I void dfs(CI x,CI lst)//Tarjan

	{

		dfn[x]=low[x]=++d,vis[S[++T]=x]=1;

		for(RI i=lnk[x];i;i=e[i].nxt)

			!dfn[e[i].to]?(dfs(e[i].to,x),Gmin(low[x],low[e[i].to]))

			:vis[e[i].to]&&Gmin(low[x],dfn[e[i].to]);

		if(dfn[x]^low[x]) return;col[x]=++cnt,vis[x]=0;

		W(S[T]^x) col[S[T]]=cnt,vis[S[T--]]=0;--T;

	}

	I void Solve()

	{

		RI i;for(i=1;i<=2*n;++i) !dfn[i]&&(dfs(i,0),0);//Tarjan

		for(i=1;i<=n;++i) if(col[i]==col[n+i]) return (void)puts("IMPOSSIBLE");//判无解

		for(puts("POSSIBLE"),i=1;i<=n;++i) F.write(col[i]>col[n+i]," \n"[i==n]);//输出一组可行解

	}

}

int main()

{

	RI i,a,b,c,d;for(F.read(n),F.read(m),i=1;i<=m;++i)

		F.read(a),F.read(b),F.read(c),F.read(d),add(a+n*(!b),c+n*d),add(c+n*(!d),a+n*b);//建边

	return Tarjan::Solve(),F.clear(),0;

}

巴特西

Tarjan在图论中的应用（三）——用Tarjan来求解2-SAT

前言

基本模型

建图

求解

代码

最新文章

热门文章