差分约束系统及2-SAT问题的应用

Aegir · 2018-09-19 11:48:07 · 个人记录

差分约束系统：

概念：

差分约束系统就是给你N个变量X_1-X_n，M个约束条件，每个约束条件形如X_i-X_j≤c_k，让你求出一组合法的解。

解法：

将约束条件变形为X_i≤X_j+c_k，于是我们可以把每个变量X_i看成一个有向图中的节点i，然后对于每个约束条件，在节点j和节点i直接连一条长度为c_k的有向边。

对于解集\{a1,...a_n\}，我们把每个a_i都加上一个常数Δ，得到的另一组解显然也是合法的（作差之后Δ刚好被消掉），所以我们考虑先求出一组负数解。

因为我们增加一个0号节点，令X_0=0，则有以下条件X_i-X_0≤0，所以我们从节点0向每个节点i连一条长度为0的有向边。

然后我们以节点0为起点跑一遍最短路，若图中存在负环，则给定的差分约束系统无解，否则，x_i=dist[i]就是差分约束系统的一组解。

有时候我们会遇到一些约束条件形如X_i-X_j≥c_k的题目。我们仍然连边求解，只是改为计算最长路，若存在正环则无解。我们也可以把条件变形为X_j-X_i≤-c_k，再按照最短路进行计算。

题目：

[SCOI2011]糖果

我们设siz[x]表示的是第x个小朋友的糖果数，分析题目中的五个条件：

siz[u] == siz[v]$，连边$e(u,v)=0,e(v,u)=0
siz[u] < siz[v]$，相当于$siz[v]-siz[u]≥1$，连边$e(u,v)=1
siz[u] ≥ siz[v]$，相当于$siz[u]-siz[v]≥0$，连边$e(v,u)=0
siz[u] > siz[v]$，相当于$siz[u]-siz[v]≥1$，连边$e(v,u)=1
siz[u] ≤ siz[v]$，相当于$siz[v]-siz[u]≥0$，连边$e(u,v)=0

然后要保证每个小朋友都能分到一个糖果，所以有siz[i]-siz[0]≥1，（siz[0]=0），所以建立一个0号节点，向每个节点i连一条边权为1的边。

然后跑一遍最长路即可（出现正环就输出-1），ans=\sum_{i=1}^ndis[i]。

PS：出题人卡Spfa，这题可以用Tarjan缩点后拓扑排序做，用差分约束做的话，在连边e(0,i)=1的时候要倒序连边（Spfa和输入顺序有关），同时还要加上SLF优化。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 200010;

int n, k, tot;
int Head[MAXN], ver[MAXN << 1], Next[MAXN << 1], edge[MAXN << 1];
int dis[MAXN], cnt[MAXN], vis[MAXN];
int h, t, q[MAXN << 1];

void add(int u, int v, int e)
{
    ver[++tot] = v;
    Next[tot] = Head[u];
    Head[u] = tot;
    edge[tot] = e;
}

bool spfa()
{
    memset(dis, 0xcf, sizeof(dis));
    q[h = t = MAXN] = 0;
    vis[0] = 1, dis[0] = cnt[0] = 0;
    while(h <= t)
    {
        int x = q[h++]; vis[x] = 0;
        for(int i = Head[x]; i; i = Next[i])
        {
            int y = ver[i], z = edge[i];
            if(dis[y] < dis[x] + z)
            {
                dis[y] = dis[x] + z;
                cnt[y] = cnt[x] + 1;
                if(cnt[y] > n) return 1;
                if(!vis[y])
                {
                    if(h <= t && dis[y] > dis[q[h]]) q[--h] = y;
                    else q[++t] = y;
                    vis[y] = 1;
                }
            }
        }
    }
    return 0;
}

int main()
{
    scanf("%d %d", &n, &k);
    for(int i = 1; i <= k; ++i)
    {
        int x, u, v;
        scanf("%d %d %d", &x, &u, &v);
        if(x == 1) add(u, v, 0), add(v, u, 0);
        if(x == 2) add(u, v, 1);
        if(x == 3) add(v, u, 0);
        if(x == 4) add(v, u, 1);
        if(x == 5) add(u, v, 0);
    }
    for(int i = n; i; --i) add(0, i, 1);
    if(spfa()) puts("-1");
    else
    {
        long long ans = 0;
        for(int i = 1; i <= n; ++i) ans += dis[i];
        printf("%lld\n", ans);
    }
    return 0;
}

2-SAT

概念：

有N个变量，每个变量只有两种可能A_{i,0},A_{i,1}。

有M个条件，每个条件形如：若A_i=A_{i,p}，则A_j=A_{j,q}。

我们的任务就是求出是否存在对N个变量的合法赋值（有时还需要构造方案）。

做法：

建立2N个节点的有向图，每个变量A_i对应两个节点i,i+N。
对条件“若A_i=A_{i,p}，则A_j=A_{j,q}”。连边e(i+p*N,j+q*N)。
如果在给出的M个限制条件中，原命题和逆否命题不一定成对出现，还需连边e(j+(1-q)*N,i+(1-p)*N)。
用Tarjan算法求出图中的所有强联通分量
若存在i,i+N属于同一个强连通分量，则问题无解，否则问题有解。

补充一下第三点（当初就是没有看懂这里）：

首先是一点概念：

命题：三角形内角和为180°
逆命题：内角和为180°的是三角形
否命题：不是三角形的内角和不为180°
逆否命题：内角和不是180°的不是三角形

然后有一个很显然的结论：命题与逆否命题的真假性是一样的

选A_{i,p}就必须选A_{j,q}，那么我们先“逆一下”，从A_{j,q}到A_{i,p}，再“否一下”，不选A_{j,q}就一定不选A_{i,p}，这是显然成立的。

因此在原来的限制条件中，如果原命题和逆否命题不成对出现，我们就要手动连一下边。

题目：[NOI2017]游戏

我们可以先忽略x地图，这样所有的地图都适合且仅适合两种赛车了。

对于每场游戏，设i表示该地图适合的第一种赛车，i^{'}表示适合的第二种赛车。

对于每个限制条件，设u为第i场游戏使用型号为h_i的赛车的点，v为第j场游戏使用型号为h_j的赛车的点。

如果第i场游戏的地图不适合赛车h_i，不做任何操作
如果第i场游戏的地图适合赛车h_i，但是第j场游戏的地图不适合赛车h_j，那么连边e(u, u^{'})，表示选了u就一定无解。
如果第i场游戏的地图适合赛车h_i，第j场游戏的地图也适合赛车h_j，那么连边e(u,v)，表示选了u就必须选v，再连边e(v^{'},u^{'})，表示逆否命题（不选u就必须不选v）。

连完边后跑一遍强联通分量判断是否有解即可，若有解，我们需要构造一种方案。

现在考虑x地图，注意到x地图最多只有8张，我们可以考虑暴力枚举x地图地图不适合赛车A或不适合赛车B，这样每种地图就都只适合两种赛车了。

构造方案：

先把缩点之后的新图进行拓扑排序，然后判断每个点i，如果i所在强连通分量的拓扑序在i^{'}所在的强连通分量的拓扑序之后，那么第i场游戏使用该地图适合的第一种赛车，否则使用第二种赛车。

注意到Tarjan求强连通分量就是按拓扑排序的逆序给出的，所以直接使用强连通分量编号判断即可。设belong[i]表示点i的强连通分量编号，如果belong[i] < belong[i^{'}]，那么使用该地图适合的第一种赛车，否则使用第二种。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;

const int MAXN = 200010;
#define fan(x) (x > n ? x - n : x + n)

int n, m, d, tot, num, top, cnt;
int Head[MAXN], ver[MAXN], Next[MAXN];
int dfn[MAXN], low[MAXN], belong[MAXN], stk[MAXN];
int i1[MAXN], j1[MAXN], xxx[MAXN];
char s[MAXN], i2[MAXN], j2[MAXN], init[MAXN];
bool ins[MAXN], flag;

void add(int u, int v)
{
    ver[++tot] = v; Next[tot] = Head[u]; Head[u] = tot;
}

void Clear()
{
    tot = num = top = cnt = 0;
    for(int i = 1; i <= (n << 1); ++i)
        Head[i] = dfn[i] = low[i] = belong[i] = 0;
}

int Get_id(int x, char c)
{
    if(s[x] == 'a') return c == 'B' ? x : x + n;
    if(s[x] == 'b' || s[x] == 'c') return c == 'A' ? x : x + n;
    if(c == 'C') return x + n;
    return x;
}

void Tarjan(int x)
{
    dfn[x] = low[x] = ++num;
    stk[++top] = x; ins[x] = 1;
    for(int i = Head[x]; i; i = Next[i])
    {
        int y = ver[i];
        if(!dfn[y])
        {
            Tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if(ins[y]) low[x] = min(low[x], low[y]);
    }
    if(dfn[x] == low[x])
    {
        ++cnt; int y;
        do
        {
            y = stk[top--]; ins[y] = 0;
            belong[y] = cnt;
        }while(y != x);
    }
}

void Build()
{
    for(int i = 1; i <= m; ++i)
        if(s[i1[i]] != 'x' && s[j1[i]] != 'x')
    {
        if(i2[i] == s[i1[i]] - 32) continue;
        int u = Get_id(i1[i], i2[i]);
        if(j2[i] == s[j1[i]] - 32) {add(u, fan(u)); continue;}
        int v = Get_id(j1[i], j2[i]);
        add(u, v), add(fan(v), fan(u));
    }
    else
    {
        char o = s[i1[i]], p = s[j1[i]];
        int x = xxx[i1[i]], y = xxx[j1[i]];
        if(o == 'x' && p == 'x')
        {
            if(i2[i] == init[x]) continue;
            int u = Get_id(i1[i], i2[i]);
            if(j2[i] == init[y]) {add(u, fan(u)); continue;}
            int v = Get_id(j1[i], j2[i]);
            add(u, v), add(fan(v), fan(u));
        }
        else if(o == 'x' && p != 'x')
        {
            if(i2[i] == init[x]) continue;
            int u = Get_id(i1[i], i2[i]);
            if(j2[i] == p - 32) {add(u, fan(u)); continue;}
            int v = Get_id(j1[i], j2[i]);
            add(u, v), add(fan(v), fan(u));
        }
        else
        {
            if(i2[i] == o - 32) continue;
            int u = Get_id(i1[i], i2[i]);
            if(j2[i] == init[y]) {add(u, fan(u)); continue;}
            int v = Get_id(j1[i], j2[i]);
            add(u, v), add(fan(v), fan(u));
        }
    }
}

bool Solve()
{
    Clear();
    Build();
    for(int i = 1; i <= (n << 1); ++i) if(!dfn[i]) Tarjan(i);
    for(int i = 1; i <= n; ++i) if(belong[i] == belong[i + n]) return 0;
    for(int i = 1; i <= n; ++i)
        if(belong[i] < belong[i + n])
    {
        if(s[i] == 'a') cout << "B";
        else if(s[i] == 'b' || s[i] == 'c') cout << "A";
        else if(init[xxx[i]] == 'A') cout << "B";
        else cout << "A";
    }
    else
    {
        if(s[i] == 'a' || s[i] == 'b') cout << "C";
        else if(s[i] == 'c') cout << "B";
        else cout << "C";
    }
    //cout << endl;
    return 1;
}

void dfs(int dep)
{
    if(dep > d)
    {
        flag = Solve();
        if(flag) exit(0);
        return;
    }
    init[dep] = 'A'; dfs(dep + 1);
    init[dep] = 'B'; dfs(dep + 1);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> d;
    cin >> s + 1;
    d = 0;
    for(int i = 1; i <= n; ++i)
        if(s[i] == 'x')
         xxx[i] = ++d;
    cin >> m;
    for(int i = 1; i <= m; ++i)
    {
        cin >> i1[i] >> i2[i];
        cin >> j1[i] >> j2[i];
    }
    dfs(1);
    if(!flag) cout << "-1";
    return 0;
}