差分约束系统学习笔记

定义

差分约束系统由n个形如$x+y\leq z$的不等式组成，注意：这里x和y是常数。

差分约束系统（System of Difference Constraints），是求解关于一组变数的特殊不等式组之方法。
如果一个系统由${\displaystyle n}$个变量和${\displaystyle m}$个约束条件组成，其中每个约束条件形如${\displaystyle x{j}-x{i}\leq b_{k}(i,j\in [1,n],k\in [1,m])}$,则称其为差分约束系统。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。 　　--维基百科

求解

我们可以把差分约束系统转换为图论中的最短路径来求解，我们来看一下下面的的不等式：

$$x-y \geq z$$

可以发现它和图论中的三角不等式极其相似

$$ disx + w{x,y} \geq dis_y$$

它相当于

$$w_{u,v} \geq dis_y- dis_x$$

注意：这里x和y是常数

我们把x和y看作点，z看作边权，所以我们要连一条$y \to x$，边权为$z$的边。

如果不等式符号相反。例如：

$$x-y\leq z$$

它可以变形为:

$$y-x \geq -z$$

我们从x向y连一条边权为-z的边即可。

在建完图后，跑一遍最短路算法便可，Dijkstra不能处理有负边权的图，所以我们要使用SPFA算法。SPFA带SLF优化会被负权图卡成指数级。

如果图不连通或者出现了负权回路则说明差分约束系统无解。

SPFA模板

void SPFA(int x)
{
    queue<int> q;
    dis[x] = 0;
    vis[x] = true;
    q.push(x);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int i = head[u]; i; i = edge[i].next)
        {
            int v = edge[i].to;
            if (dis[v] > dis[u] + edge[i].data)
            {
                dis[v] = dis[u] + edge[i].data;
                if (++cnt[v] >= n) //出现负权回路
                {
                    puts("-1");
                    exit(0);
                }
                if (vis[v] == false)
                {
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
}

例题

小K的农场

USACO05DEC 布局