差分约束总结

差分约束是一个简单的能解一种特殊的 \(n\) 元一次不等式组(或者判断无解)的算法，

其中每个不等式形如 \(x_a-x_b\le c\)，\(c\) 是常数。

差分约束利用了最短路的一个性质：

一个有向图跑完最短路后一定满足对于任意一条边 \((x,y,z)\)，有 \(dis_y\le dis_x+z\)

这个性质很简单，因为既然有了这样一条边，那么 \(dis_y\) 的范围缩小到最多只能取 \(dis_x+z\)，而且以后还可能继续缩小

然后我们把原来的不等式变换一下：\(x_a\le x_b+c\)

发现它与上面的不等式很像！

尝试建图，每个未知数 \(x_i\) 看成是图上的一个节点，

每个约束条件 \(x_i-x_j\le c_k\) 看成一条边

\(x_i\le x_j+c_k\)

于是可以建立一条有向边 \((j,i,c_k)\) (不用死记硬背，理解了这个就知道为什么这样连边了。。。)

然后跑完最短路后即可满足所有的约束条件。

不过从哪个点作为起点呢？实际上每个点都可以作为起点，所以我们建立一个超级原点 \(0\)，\(0\) 连向所有点有一条权值为 \(0\) 的边

这样，从节点 \(0\) 开始，每个点都可以走到，也就保证解出了所有的未知数。

注意，此时有额外的边 \((0,i,0)\)，说明我们约束所有的未知数 \(x_i\le 0\)

这样跑出来每个 \(dis_i\) 都不是正数...

何时存在无解和无数解？

如果有无法到达的点，则是无数解（这里没有超级原点，因为超级原点是我们为了跑出所有解而人为添加的一个点）

因为这个点无法到达，说明没有边连向它，这就意味着这个点其实是没有约束的，取任意值都满足

如果要判断的话，直接看有没有节点不连边就行

而如果出现了负环，则是无解

因为出现负环意味着根本不存在最短路径，只有更短路径

因为负边权这一存在，迫使我们使用 \(\text{SPFA}\) 这个死去的算法来帮助我们求解

而且很方便的是，它也能帮助我们判负环(无解)。。。

所以别再管什么生与死，用它就对了！

实际上，最短路求出的解一定是 \(x_i\le 0\) 时的最大解

因为我们每个 \(dis_i\) 的范围都是从 \([-\infty,+\infty]\) 缩小(松弛)到 \([-\infty,x]\)

而它最终取的是这个范围内最大的 \(x\)

所以是最大解。

意会一下就可以了（（

对应的，如果求 \(x_i\ge 0\) 时的最小解，跑最长路即可

建边时注意一下，最长路满足对于有向边 \((x,y,z)\)，\(dis_y\ge dis_x+z\)

所以如果是约束条件 \(x_i\le x_j+c_k\)

\(x_j\ge x_i-c_k\)

所以建边 \((i,j,-c_k)\)

仍然按上面的方法建一个超级源点，则每个 \(x_i\ge 0\)

此时求出的就是正整最小解。

附赠 \(\text{SPFA}\) 最短路 & 判负环

int dis[N], inque[N];
void SPFA(int node) {
    memset(inque, 0, sizeof inque);
    memset(dis, 0x3f, sizeof dis);
    queue<int> q;
    q.push(node);
    dis[node] = 0;
    while (!q.empty()) {
        int now = q.front(); q.pop();
        inque[now] = 0;
        for (int i = h[now]; i; i = a[i].n) {
            int j = a[i].t;
            if (dis[j] > dis[now] + a[i].v) {
                dis[j] = dis[now] + a[i].v;
                if (!inque[j])
                    inque[j] = 1, q.push(j);
            }
        }
    }
}
SPFA(0);

int dis[N], inque[N], cnt[N];
bool SPFA(int node) { // 判负环
    memset(inque, 0, sizeof inque);
    memset(dis, 0x3f, sizeof dis);
    memset(cnt, 0, sizeof cnt);
    queue<int> q;
    q.push(node);
    dis[node] = 0;
    cnt[node]++;
    while (!q.empty()) {
        int now = q.front(); q.pop();
        inque[now] = 0;
        for (int i = h[now]; i; i = a[i].n) {
            int j = a[i].t;
            if (dis[j] > dis[now] + a[i].v) {
                dis[j] = dis[now] + a[i].v;
                cnt[j]++;
                if (cnt[j] == n + 1) return false;
                if (!inque[j])
                    inque[j] = 1, q.push(j);
            }
        }
    }
    return true;
}
puts(SPFA(0) ? "Yes" : "No");

另外拓扑排序好像也可以判...不过不在本文讨论范围内，而且 \(\text{SPFA}\) 适用性更广，具体自己可以百度