洛谷P4782 2-SAT问题

时间:2022-05-25 01:10:44

2-SAT问题

这是一道2-SAT的模板题。对于2-SAT问题的每一个条件,我们需要把他们转化成可接受的条件。即"若变量A的赋值为x,则变量B的赋值为y",其中x,y均等于0或1。

对于每个条件我们连一条有向边,下面对于本题给出的或举例。

假如题目的限制条件为 X=1 or Y = 1 为真

那么对于这个条件,我们可以按上述方法,转换成2-SAT可接受的判定条件:

如果X=0,那么Y=1 以及 如果Y=0,那么X=1

如果题目一共给出n个变量,我们通常假定[1..n]代表变量X[i]赋值为0,[n+1..2n]代表变量x[i]赋值为1。

对于上面的例子,即在(x,y+n),(y,x+n)连有向边即可。

在判定是否矛盾的时候,只要用tarjan找出所有强联通分量,如果x与x+n在同一强联通分量中,说明问题无解。否则有解。

那么如何构造一组解呢?

首先,在一个SCC中,只要确定了一个变量的值,那么该SCC中其他变量的值也确定了。我们再考虑一个点,假设这个点在原图中没有出度,那么这个点的取值将不会影响其他店。

那么我们得到启发,把所有强联通分量缩点,依次取出度为0的点的赋值情况即可。

找出度为0的点,我们可以用tarjan缩点后重构图,但是注意要建反图,再利用topsort找入度为0的点的性质topsort一次。

缩点之后我们可以发现scc[x],scc[x+n]是原图对称的两个点,假如有两个点在原图中属于同一个scc,那么他们的对称点也一定属于同一个scc(感性理解。。大概是逆否命题的感觉?)

那么我们记opp[scc[x]]=scc[x+n], opp[scc[x+n]]=scc[x];

当我们把队首元素取出来的时候,用val记录该ssc中点的赋值情况,意思为该联通分量中所有原图的点(小于n的点)的取值合法,初始值为-1。如果val=-1,那么val[s]=0, val[opp[s]]=1。

这样赋值的意义是,如果该scc中有某变量取值是0,那么代表他的取值的点一定小于n,令改点为s,最后我们在构造解的时候直接取val[scc[s]]=0即可。如果该scc中有某变量取值是1,那么他的对称点所在的scc被赋值成了1,也就是说序号小于n的那个点所在的scc的val为1,构造解的时候同理,直接取值即可。

下面是这种构造方法的代码:

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define full(a, b) memset(a, b, sizeof a)
using namespace std;
typedef long long ll;
inline int lowbit(int x){ return x & (-x); }
inline int read(){
int X = 0, w = 0; char ch = 0;
while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }
while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
return w ? -X : X;
}
inline int gcd(int a, int b){ return a % b ? gcd(b, a % b) : b; }
inline int lcm(int a, int b){ return a / gcd(a, b) * b; }
template<typename T>
inline T max(T x, T y, T z){ return max(max(x, y), z); }
template<typename T>
inline T min(T x, T y, T z){ return min(min(x, y), z); }
template<typename A, typename B, typename C>
inline A fpow(A x, B p, C lyd){
A ans = 1;
for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;
return ans;
}
const int N = 2000005;
int n, m, cnt, k, head[N], dfn[N], low[N], ins[N], tot, scc[N];
int h[N], t, deg[N], val[N], opp[N];
struct Edge { int v, next; } edge[N<<2], e[N<<2];
stack<int> st; void addEdge(int a, int b){
edge[cnt].v = b, edge[cnt].next = head[a], head[a] = cnt ++;
} void add(int a, int b){
e[t].v = b, e[t].next = h[a], h[a] = t ++;
} void tarjan(int s){
dfn[s] = low[s] = ++k;
ins[s] = true, st.push(s);
for(int i = head[s]; i != -1; i = edge[i].next){
int u = edge[i].v;
if(!dfn[u]){
tarjan(u);
low[s] = min(low[s], low[u]);
}
else if(ins[u])
low[s] = min(low[s], dfn[u]);
}
if(dfn[s] == low[s]){
tot ++; int cur = 0;
do{
cur = st.top(); st.pop();
ins[cur] = false, scc[cur] = tot;
}while(cur != s);
}
} void topSort(){
full(val, -1), full(h, -1);
for(int s = 1; s <= 2 * n; s ++){
for(int i = head[s]; i != -1; i = edge[i].next){
int u = edge[i].v;
if(scc[s] != scc[u]) add(scc[u], scc[s]), deg[scc[s]] ++;
}
}
queue<int> q;
for(int i = 1; i <= tot; i ++){
if(!deg[i]) q.push(i);
}
while(!q.empty()){
int s = q.front(); q.pop();
if(val[s] == -1) val[s] = 0, val[opp[s]] = 1;
for(int i = h[s]; i != -1; i = e[i].next){
int u = e[i].v;
if(!--deg[u]) q.push(u);
}
}
for(int i = 1; i <= n; i ++){
if(val[scc[i]]) printf("1 ");
else printf("0 ");
}
puts("");
} int main(){ full(head, -1);
n = read(), m = read();
for(int i = 0; i < m; i ++){
int x = read(), a = read(), y = read(), b = read();
addEdge(x + (1 - a) * n, y + b * n);
addEdge(y + (1 - b) * n, x + a * n);
}
for(int i = 1; i <= 2 * n; i ++){
if(!dfn[i]) tarjan(i);
}
bool flag = false;
for(int i = 1; i <= n; i ++){
if(scc[i] == scc[i + n]){
printf("IMPOSSIBLE\n");
flag = true;
break;
}
}
if(!flag){
printf("POSSIBLE\n");
for(int i = 1; i <= n; i ++){
opp[scc[i]] = scc[i + n], opp[scc[i + n]] = scc[i];
}
topSort();
}
return 0;
}

但是,其实我们考虑tarjan的本质,是一次dfs,联通分量序号越小的在图的越底层。

也就是说我们用tarjan找到的scc其实已经满足我们需要的自底向上的性质了。

我们对每个点的取值情况,直接取靠后的ssc即可。

下面给出代码,无需重构图:

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define full(a, b) memset(a, b, sizeof a)
using namespace std;
typedef long long ll;
inline int lowbit(int x){ return x & (-x); }
inline int read(){
int X = 0, w = 0; char ch = 0;
while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }
while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
return w ? -X : X;
}
inline int gcd(int a, int b){ return a % b ? gcd(b, a % b) : b; }
inline int lcm(int a, int b){ return a / gcd(a, b) * b; }
template<typename T>
inline T max(T x, T y, T z){ return max(max(x, y), z); }
template<typename T>
inline T min(T x, T y, T z){ return min(min(x, y), z); }
template<typename A, typename B, typename C>
inline A fpow(A x, B p, C lyd){
A ans = 1;
for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;
return ans;
}
const int N = 2000005;
int n, m, cnt, k, head[N], dfn[N], low[N], ins[N], tot, scc[N];
struct Edge { int v, next; } edge[N<<2];
stack<int> st; void addEdge(int a, int b){
edge[cnt].v = b, edge[cnt].next = head[a], head[a] = cnt ++;
} void tarjan(int s){
dfn[s] = low[s] = ++k;
ins[s] = true, st.push(s);
for(int i = head[s]; i != -1; i = edge[i].next){
int u = edge[i].v;
if(!dfn[u]){
tarjan(u);
low[s] = min(low[s], low[u]);
}
else if(ins[u])
low[s] = min(low[s], dfn[u]);
}
if(dfn[s] == low[s]){
tot ++; int cur = 0;
do{
cur = st.top(); st.pop();
ins[cur] = false, scc[cur] = tot;
}while(cur != s);
}
} int main(){ full(head, -1);
n = read(), m = read();
for(int i = 0; i < m; i ++){
int x = read(), a = read(), y = read(), b = read();
addEdge(x + (1 - a) * n, y + b * n);
addEdge(y + (1 - b) * n, x + a * n);
}
for(int i = 1; i <= 2 * n; i ++){
if(!dfn[i]) tarjan(i);
}
bool flag = false;
for(int i = 1; i <= n; i ++){
if(scc[i] == scc[i + n]){
printf("IMPOSSIBLE\n");
flag = true;
break;
}
}
if(!flag){
printf("POSSIBLE\n");
for(int i = 1; i <= n; i ++)
printf("%d ", scc[i] > scc[i + n]);
}
return 0;
}