P4659 [BalticOI 2008]阀门 题解

分析

一道 2-SAT 模板题，但是很不明白为什么其他题解没有点明 2-SAT。

设第 $i$ 个开关状态为 $x_i\left(x_i\in\left\{0,1\right\}\right)$，首先发现答案必须满足对于每一条管道，都有 $x_a=s_a$ 或 $x_b=s_b$。所以本题是有 $m$ 个未知量和 $n$ 个约束的 2-SAT，直接套板子即可。

代码

#include<bits/stdc++.h>
const int maxn=2000005;
const int maxe=2000005;
using namespace std;
int N,M,tot,lnk[maxn],nxt[maxe],son[maxe];
int tim,dfn[maxn],low[maxn],fa[maxn],top,stk[maxn],scn,scc[maxn];
void add_e(int x,int y){son[++tot]=y,nxt[tot]=lnk[x],lnk[x]=tot;}
void Tarjan(int id){
    dfn[stk[++top]=id]=low[id]=++tim;
    for(int j=lnk[id];j;j=nxt[j])
        if(!dfn[son[j]]) Tarjan(son[j]),low[id]=min(low[id],low[son[j]]);else
        if(!fa [son[j]])                low[id]=min(low[id],dfn[son[j]]);
    if(dfn[id]==low[id]) for(scn++;true;)
        if(fa[stk[top]]=id,scc[stk[top]]=scn,stk[top--]==id) return;
}
int read(){
    int f=1,ret=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f; ch=getchar();}
    while( isdigit(ch)) ret=(ret<<3)+(ret<<1)+(ch&15),ch=getchar();
    return f*ret;
}
int main(){
    M=read(),N=read();
    for(int i=1;i<=M;i++){
        int x=read(),a=read(),y=read(),b=read();
        add_e(x+N*(a^1),y+N*b);
        add_e(y+N*(b^1),x+N*a);
    }
    for(int i=1;i<=N;i++) if(!dfn[  i]) Tarjan(  i);
    for(int i=1;i<=N;i++) if(!dfn[N+i]) Tarjan(N+i);
    for(int i=1;i<=N;i++) if(fa[i]==fa[N+i]){printf("IMPOSSIBLE\n");return 0;}
    for(int i=1;i<=N;i++) printf("%d\n",scc[i]>scc[N+i]);
    return 0;
}