2-SAT 算法

一般 2-SAT 问题

有个布尔变量，另有个需要满足的条件，每个条件的形式都是「为 true / false 或为 true / false」。比如「为真或为假」、「为假或为假」。

2-SAT 问题的目标是给每个变量赋值使得所有条件得到满足。

这个算法的精髓就是把这种问题转化为图论问题，然后用 Tarjan SCC 缩点算法解决。

思路

我们把这个需要满足的条件看成一个图。这个图中有个点。点和点分别代表了这个布尔变量取和取的情况。这个图中的每一条边代表的就是如果你选了情况，那么你就必须选情况。容易发现，每一个强联通分量里面，如果你选了一种情况，那么其他的情况也必须选择。

假设我们把每一个为真/假看为一个条件。题目给的是「条件 1 成立或条件 2 成立」这种限制关系。假设条件 1 成立为，条件 2 成立为，那么原式就可以被转化为（表示逻辑或）。因为上面的边代表的不是或关系而是蕴含关系。所以我们尝试把它转化为蕴含关系：如果你选了，那么你就必须选和如果你选了，那么你就必须选。即。这种蕴含关系是可以传递的，也就正好证明了上面建图的正确性。

注意：不能被转化为。因为若时，，而。

于是我们就可以开始拆点建图：假设值为或值为，那么条件 1 就为「值为」，条件 2 就为「值为」。那么连边就是从「值不为」连向「值为」，即；和从「值不为」连向「值为」，即。

那么检查能不能使个限制条件都满足，那么就检查是否存在使点和点在同一个强连通分量里。因为两个点在同一个强连通分量里的话就意味着这两个情况都要被选。而一个变量是不可能同时把值赋为和的。所以如果点和点在同一个强连通分量里，那么就不能使个限制条件都满足。否则就能使个限制条件满足。

现在我们需要构造出一种可行解。首先我们可以先把所有的强联通分量都缩成一个点，这样整个图就会变成一个 DAG。然后分析：之前的连边会导致一个变量的两个取值是有先后关系的。比如说：。因为说，有可能会有多个点连向同一个点，所以，我们需要让拓扑序越大的先被满足，就比如刚刚例子中的。这样，就可以一步一步，递推回去，然后满足拓扑序小的。这样就不会产生取值上的矛盾了。

于是，我们就要在两个点，和中，选择拓扑序大的那一个。

而因为在 Tarjan 求 SCC 的时候，SCC 的编号其实就是拓扑序给它倒过来。因为是先从前往后递，然后赋值，最后从后往前归的。所以就转化为，在和中，选择 SCC 编号更小的那一个。

因为表示的是，表示的是。所以就可以转化为或者。

Code:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+6;
const int M = 2e6+12;
struct Edge{
    int to, nxt;
}edge[M<<1];
int h[M], cnt;
void add(int u, int v){
    edge[++cnt] = {v, h[u]};
    h[u] = cnt;
}
int n, m;
int st[M], top, len, dfnidx;
int sccin[M];
int dfn[M], low[M];
void tarjan(int x){
    low[x] = dfn[x] = ++dfnidx;
    st[++top] = x;
    for(int i=h[x];i;i=edge[i].nxt){
        int v = edge[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[x] = min(low[x], low[v]);
        }else if(!sccin[v]){
            low[x] = min(low[x], dfn[v]);
        }
    }
    if(low[x] == dfn[x]){
        int lstpop = 0;
        len ++;
        do{
            lstpop = st[top];
            top --;
            sccin[lstpop] = len;
        }while(lstpop != x);
    }
}
bool check(){
    for(int i=1;i<=n;i++){
        if(sccin[i] == sccin[i+n]) return 0;
    }
    return 1;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x, y, a, b;
        cin>>x>>a>>y>>b;
        add(x+(!a)*n, y+b*n);
        add(y+(!b)*n, x+a*n);
    }
    for(int i=1;i<=n*2;i++){
        if(!dfn[i]) tarjan(i);
    }
    if(check()){
        cout<<"POSSIBLE\n";
        for(int i=1;i<=n;i++){
            cout<<(sccin[i] > sccin[i+n])<<' ';
        }
    }else{
        cout<<"IMPOSSIBLE\n";
    }
    return 0;
}

前后缀优化建图

P6378 Riddle

个点条边的无向图被分成个部分。每个部分包含一些点。

请选择一些关键点，使得每个部分恰有一个关键点，且每条边至少有一个端点是关键点。

若可能选出请输出 TAK，否则输出 NIE。

这道题的朴素算法就是：首先每条边至少有一个端点是关键点是简单的，若存在边，则在 2-SAT 中连边：。然后对于每一个部分，将其中的「选每一个点」向「不选其它点」连边，即。然后跑 2-SAT 求是否存在选法即可。

但是这道题的是级别的，按照上述方法连边那么边数就会变为级别的，就会喜提 MLE。于是我们要考虑如何优化建图。

对于每条边至少有一个端点是关键点这个例子，因为它的边是级别的，所以没必要优化。现在要优化的是对每个部分恰有一个关键点这个限制的连边的优化。

我们首先举个例子，把有个点的一个「部分」的原始建边方式画出来：

这里介绍一个 Trick：将一个点连向其它所有点等价于将连向的后缀和将连向的前缀。

于是我们可以先把的前缀和后缀画出来：

最后连边方式就变为了这样：

于是我们的点数和边数都缩减到了级别，然后就不会出现类似 MLE 的情况了。

为了好连边，我们将状态设置编号为，辅助状态设为，辅助状态设为。

最后跑一遍 2-SAT 即可得出答案。

核心代码-建边方式：

...
for(int i=1;i<=k;i++){
    cin>>plen;
    for(int j=1;j<=plen;j++){
        cin>>part[j];
        add(part[j]+2*n, part[j]+n);
        add(part[j]+3*n, part[j]+n);
    }
    for(int j=1;j<plen;j++){
        add(part[j+1]+2*n, part[j]+2*n);
        add(part[j]+3*n, part[j+1]+3*n);
        add(part[j+1], part[j]+2*n);
        add(part[j], part[j+1]+3*n);
    }
}
for(int i=1;i<=2*n;i++){
    if(!dfn[i]) dfs(i);
}
...

线段树优化建图

ARC069F Flags

Snuke 将个标志放在一条线上。

第个标志可以放置在坐标或坐标上。

Snuke 认为当他们中的两个之间的最小距离更大时，标志看起来更好。找出的最大可能值。

看到这道题，首先就可以二分答案，二分的过程中有个，如果可以成为答案的话就把答案设为，然后继续往大的搜。

二分的过程中，这个就是钦定现在的最小距离。看看这个时候，能否符合距离要求。

因为每一个点只有 2 个选择，很容易会想到 2-SAT。具体的过程就是：设点能选的两个位置分别为和。现在考虑两个点，如果，那么这个是很明显的不符合要求的，那么点在选位置的时候，点只能选位置。也就是从「选择位置」这种情况向「选择位置」连边。、、同理。

但这样下来，时间和空间复杂度都是级别的。我们需要一种更快且更省空间的建图方式。

现在我们设「选择位置」和「选择位置」互为反点。先把所有塞到一个数组里面。也就是说，其实连向的点全部都是所有数组里值域在的点的反点。对于这种区间连边的建图优化，可以使用线段树优化建图。

线段树优化建图，就是把连接区间的操作放在了线段树上，使每一次修改的时间降到了级别，总时间、空间就降到了级别。下图是一个的线段树图像：

每个点的右下角就是它在 2-SAT 图中被赋予的编号，编号为的是真实点，其它的就是辅助建图的点。每两个辅助节点中间黑色的边就是辅助点之间从上至下连的辅助边。为了使建图更方便用的。

上面的浅紫色部分其实就是把全部塞进一个数组，然后排序过后的结果。这样做是为了使连边的范围变为一个区间，方便连边。每一个浅紫色结点都对应线段树上的区间。每一个浅紫色结点其实只是线段树上的一个辅助点，这里为了方便给它打上了标号。并不代表它就是真实状态。

而红色的边就代表其实下面的深蓝色节点，即真实状态不是上面辅助点的儿子，而是它的反点。因为每一次连边是给一个区间的每一个点的反点连边的。

现在举个例子：假设点要开始连边了。先定值域范围：。这些点中必定包含。而又不能将边连向自己的反点，所以首先将辅助点（即真实点）排除。假设这个值域范围正好包含范围的话，那么就连区间。即范围。

连边之后的图是这样的：

这里蓝色的边是真正连了的边，橘色的边就是这些蓝色的边会影响到的边。这样就可以连少数条边而达到级别的效果了。

最后就是正常跑 2-SAT，然后检查、输出。这道题就做完了。

核心代码：

#define diff(x) (x>n?x-n:x+n)
struct Flags{
    int pos, idx;
}flag[N];
int flagpos[N];
bool cmp(Flags x, Flags y){
    return x.pos < y.pos;
}
// 线段树部分
namespace Seg_Tr{
    int id[M<<3];
    int idcnt;
    void build(int x, int l, int r){
        id[x] = ++idcnt;
        if(l==r){
            add(id[x], diff(flag[l].idx));
            return ;
        }
        int mid = l+r>>1;
        build(x<<1, l, mid);
        build(x<<1|1, mid+1, r);
        add(id[x], id[x<<1]);
        add(id[x], id[x<<1|1]);
    }
    void connect(int x, int l, int r, int ql, int qr, int from){
        if(qr < ql) return ;
        if(ql<=l&&r<=qr){
            add(from, id[x]);
            return ;
        }
        int mid = l+r>>1;
        if(ql<=mid) connect(x<<1, l, mid, ql, qr, from);
        if(qr>mid) connect(x<<1|1, mid+1, r, ql, qr, from);
    }
}
// 执行线段树辅助建图、并跑 2-SAT 部分
bool check(int lim){
    idcnt = 2*n;
    build(1, 1, 2*n);
    for(int i=1;i<=2*n;i++){
        int l = lower_bound(flagpos+1, flagpos+1+2*n, flagpos[i]-lim+1) - flagpos;
        int r = upper_bound(flagpos+1, flagpos+1+2*n, flagpos[i]+lim-1) - flagpos - 1;
        connect(1, 1, 2*n, l, i-1, flag[i].idx);
        connect(1, 1, 2*n, i+1, r, flag[i].idx);
    }
    for(int i=1;i<=2*n;i++){ //跑 2-SAT
        if(!dfn[i]) tarjan(i);
    }
    for(int i=1;i<=n;i++){// 检查是否有解
        if(sccin[i] == sccin[i+n]) return 0;
    }
    return 1;
}

~~■■，做完了才发现这是一道铜牌题，牛■！~~

Link: 2-SAT 算法练习题单

警示后人：写 2-SAT 的时候非常容易把数组大小开小，请在交代码之前检查自己数组的大小（也就是那个常数 N 的值）！我就遭过好几次了