差分约束系统(System of Difference Constraints)的基本概念,思路和用法以及例题总结。

基本概念

差分约束系统(System of Difference Constraints),是求解关于一组变数的特殊不等式组的方法。

如果一个系统由n个变量和m个约束条件组成,其中每个约束条件形如 xixj<=bk(i,j[1,n], k[1,m])x_i-x_j<=b_k (i, j\in[1, n],\ k\in[1, m]),则称其为差分约束系统。

代数解法

求差分约束的最大值,可以将某几个不等式加减组合形成我们需要求解的不等式,然后得到答案。

图论解法

差分约束系统都可以转化成单源最短路(或者最长路)问题。

转化:

x[i]x[j]<=b[k]x[i]-x[j]<=b[k] 移项转化为 x[i]<=x[j]+b[k]x[i]<=x[j]+b[k] ,形式上与松弛操作dis[v] = dis[u] + edge[u][v]相似。

则我们将每个不等式转化成一条边,x[i] - x[j] <= b[k]转化为由 j 到 i ,边权为 b[k] 的有向边。

则要求x[n - 1] - x[0]的最大值,可以转化为求 0 -> n - 1的最短路;

反之,最小值将转化为两点之间的最长路问题。

一种理解方式

x[i] - x[j] <= b[k]的最大值,则需要求这些b[k]中最小的,即约束最严苛的一个不等式。

反之,求x[i] - x[j] >= b[k]的最小值,则需要求这些b[k]中最大的值。

解的存在性判断

如同最短路问题中的负环 / 终点不联通情况,在求解差分约束问题时同样存在对应版本的特殊情况。

1 - 最大值负环 / 最小值正环

若求解最短路负环,则最短路可以是无限小。此时我们认为最大值和最短路不存在。

**对应的SPFA判断操作:**若某一点的入队次数大于节点数,则认为不存在。

2 - 终点未联通

表示两点之间没有约束关系,最大值和最小值为正负无穷。实现过程中由dis[n - 1] = INF来表示。

例题

  • 题目链接:洛谷P1993 - 小K的农场

  • 题意转化:

    题目中给了三种情况,分别是:

    1. a - b <= c
    2. a - b >= c
    3. a == b

    分别转换成 a >= b + cb >= a - c

    要求判断是否条件不矛盾,当条件有环时则说明矛盾(如 a > b, b > c, c > a),则题目可以转化为判断是否有环。对于以上的形式:

    1. 建立b --> a, cost = c的边
    2. 建立a --> b, cost = -c的边
    3. 建立a <-> b, cost = 0的边

    对于大于等于,求最小值,最长路,则求是否存在正环(若整理成小于等于则恰好相反)。

  • 优化点

    对于这道题,我们只需要判断是否有环,所以我们可以采用DFS形式的SPFA。深度优先使得算法在查找环时的效率倍增。但是对于求距离的题目,则传统BFS更优。

    超级源点 0,通过边权为0的边连通每一个点,使图联通。

    链式前向星存图。

  • 示例代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e4 + 5;
const int INF = 1 << 30;
int n, m;

struct Edge
{
    int to, cost, next;
} edge[MAXN << 2];
int head[MAXN << 2];
void add_edge(int u, int v, int w)
{
    static int cnt = 0;
    cnt++;
    edge[cnt].to = v;
    edge[cnt].cost = w;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

int vis[MAXN], dis[MAXN], flag = 0;
void spfa(int u)
{
    if (flag) return;
    vis[u] = 1;
    for (int i = head[u]; i; i = edge[i].next)
    {
        int v = edge[i].to, w = edge[i].cost;
        if (dis[v] < dis[u] + w)
        {
            if (vis[v] || flag)
            {
                flag = 1; break;
            }
            dis[v] = dis[u] + w;
            spfa(v);
        }
    }
    vis[u] = 0;
}

int main()
{
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int opt, a, b, c;
        cin >> opt >> a >> b;
        switch (opt)
        {
            case 1:
            {
                cin >> c; add_edge(b, a, c);
                break;
            }
            case 2:
            {
                cin >> c; add_edge(a, b, -c);
                break;
            }
            case 3:
            {
                add_edge(a, b, 0); add_edge(b, a, 0);
                break;
            }
            default: break;
        }
    }

    for (int i = 1; i <= n; i++)
    {
        add_edge(0, i, 0); dis[i] = -INF;
    }

    spfa(0); 
    cout << ((flag)? "No\n": "Yes\n");
    return 0;
}

小结

以上就是差分约束的基本总结以及例题。

冻葱Tewi 于 2019-07-19