初探差分约束系统

· · 个人记录

1. 概述

前置知识：单源最短路径，负环。

差分约束系统是一种特殊的 n 元一次不等式组，其模板问题为：给定 n 个变量 x_1,\cdots ,x_n 和 m 个约束条件，每个约束条件形如 x_i-x_j\le c_k。这也是“差分”的由来。要求求解一组这个不等式组的解。

差分约束系统实际是应用了最短路算法的松弛的思想，是一类最短路模型。借鉴其思想可以解决很多性质相类似的题目。

2. 算法思想

观察每个约束条件 x_i-x_j\le c_k，等价于 x_i\le x_j+c_k。不难发现这与最短路中的三角形不等式 dis_v\le dis_u+w(u,v) 相类似。其中，dis_i 表示起点到节点 i 的最短路长度，w(u,v) 表示节点 u 到节点 v 的边权。

于是可以把 n 个变量当做 n 个节点建一张图。对于每个约束条件，从节点 j 向 i 连一条边权为 c_k 的有向边。只要跑一次最短路，dis_i 即为一组合法的解。

但是，如果以这些变量中的任意一个作为起点，这会使得该变量被钦定为 dis=0，可能使最终的答案跑出来十分难看。而且这只适用于 Bellman-Ford，因为 SPFA 只能处理同一连通块，无法处理非连通图。

我们不妨求解一组非正数解，即 \forall i,dis_i\le0。这就相当于增加了约束条件 \forall i,x_i-x_0\le c_0，其中 dis_0=0,c_0=0。相当于从 0 号节点向其余节点连边权为 0 的有向边。这也保证了图连通。

同时注意到对于一组合法的解 dis_i，dis_i+\Delta 也必定是一组合法的解，因为差分使得 \Delta 消去。运用这个性质，我们可以轻松得到一组正数解甚至可以满足更强条件的解。当然通过改变 0 号节点的边权也能达到相同目的。

此时以 0 号节点为起点，跑一遍单源最短路求解 dis_i 即可。如果出现了负环，则无解。

考虑以下约束条件：

\begin{cases}x_1-x_2\le 1 &(1)\\x_2-x_3\le -5&(2)\\x_3-x_1\le 2&(3)\end{cases}

把图建出来以后，很明显是个负环。

根据不等式的可加性，(1)+(2)+(3) 可以得到 0<-2，显然不成立，无解。因此，若图中出现负环，则该差分约束系统为无解。

使用 SPFA 即可判负环并求解 dis，时间复杂度最坏为 O(nm)。Bellman-Ford 也可以。

关于判负环的方法，详情请看P3385 【模板】负环 题解，这里不再赘述。

3. 参考代码

模板题入口。本代码需要 C++11。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<climits>
using namespace std;

const int MAXN=5e3+5;
int n,m;
struct node
{
    int to,v;
};
vector<node> edge[MAXN];
int dis[MAXN],cnt[MAXN];
bool visit[MAXN];

bool spfa(void)//模板 spfa
{
    for(int i=1;i<=n;i++)   dis[i]=INT_MAX;
    dis[0]=0;
    queue<int> q;
    q.push(0);
    visit[0]=true;
    while(!q.empty())
    {
        const int u=q.front();
        q.pop();
        visit[u]=false;
        for(auto it:edge[u])
        {
            const int v=it.to,w=it.v;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if(!visit[v])
                {
                    visit[v]=true;
                    cnt[v]++;
                    if(cnt[v]>=n+1) return false;//存在负环
                    q.push(v);
                }
            }
        }
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;cin>>u>>v>>w;
        edge[v].push_back(node{u,w});//根据约束条件来建图
    }
    for(int i=1;i<=n;i++)//新建0号节点并建图
     edge[0].push_back(node{i,0});
    if(!spfa())
    {
        cout<<"NO"<<endl;
        return 0; 
    }
    for(int i=1;i<=n;i++)   cout<<dis[i]<<endl;
    return 0;
}

4. 扩展

然而很多时候题目给定的约束条件不会这么裸，经常有变形。我们只要通过某些手段，将其变形为等价的不等式求解即可。下面是一些常见的变形。

等价于 x_j-x_i\le c_k，或者跑最长路。

等价于 x_i-x_j\le0 且 x_j-x_i\le 0。

等价于 x_i\ge x_j+1，即 x_i-x_j\ge 1。

一种常用的化乘为加的 trick：用 \log 来计算，相关技巧的应用可以参考这道题（非差分约束）。那么原不等式就等价于 \log x_i-\log x_j\le \log c_k。

不少题目的约束条件还需要我们根据题意构造得到，难度也就更大些。还要尤其注意部分题目的隐含条件。

5. 例题

广告：差分约束基础应用题单。

差分约束系统的应用通常分为三种：求不等式组解的最大值，最小值，判断有无解。

对于求最大值，我们有 x_i\le x_j+c_k，这刚好对应了跑完最短路后，x_0 为起点的 dis_i。加上 x_0=0，于是就有 x_i=dis_i，即为最大值。

而求最小值，约束条件就都变形为 x_i\ge x_j+c_j。跑最长路即可。具体实现就跟最短路的相反即可。比如dis=-INF，松弛取max。

判断有无解即为判断负环，最长路对应正环。方法也都是看入队次数。

5.1 P3275 [SCOI2011]糖果

尽管本题正解不是差分约束，但是可以当做差分约束基础题来做，只需要基本的不等式变形技巧。

对于取不到等号的，比如 x_1<x_2，由于 x_1,x_2 为整数，所以可以等价于 x_1\le x_2-1。

不过在这里我们变形为大于等于号，跑最长路。因为题目要求求出最小值。

然后一个隐含条件是每个小朋友分到的糖果数必须是正整数，因此我们钦定 x_i\ge 1，即 x_i-x_0\ge 1，相当于从 0 号点向其余节点连边权为 1 的有向边。

答案即为 \sum_{i=1}^n dis_i。

不过朴素的 SPFA 会 TLE。但在本题一种奇怪的优化方案是 0 号点从 n\sim 1 号点来加边，而非 1\sim n，至于原理只是针对数据卡过去而已（具体的并不清楚）。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<deque>
#include<cstring>
#include<numeric>
#include<climits>
using namespace std;

const int MAXN=1e5+5;
int n,m;
struct node
{
    int to,v;
};
vector<node> edge[MAXN];
int dis[MAXN],cnt[MAXN];
bool visit[MAXN];

bool spfa(void)
{
    for(int i=1;i<=n;i++)   dis[i]=INT_MIN;
    dis[0]=0;
    deque<int> q;//貌似比 queue 快一些。当然可以手写。
    q.push_front(0);
    visit[0]=true;
    while(!q.empty())
    {
        const int u=q.front();
        q.pop_front();
        visit[u]=false;
        for(auto it:edge[u])
        {
            const int v=it.to,w=it.v;
            if(dis[v]<dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if(!visit[v])
                {
                    visit[v]=true;
                    cnt[v]++;
                    if(cnt[v]>=n+1) return false;
                     q.push_front(v);
                }
            }
        }
    }
    return true;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,a,b;cin>>x>>a>>b;
        if(x==1)
        {
            edge[a].push_back(node{b,0});
            edge[b].push_back(node{a,0});
        }
        if(x==2)
           edge[a].push_back(node{b,1});
        if(x==3)
            edge[b].push_back(node{a,0});
        if(x==4)
            edge[b].push_back(node{a,1});
        if(x==5)
            edge[a].push_back(node{b,0}); 
    }
    for(int i=n;i>=1;i--)//奇怪的优化
        edge[0].push_back(node{i,1});
    if(!spfa())
    {
        cout<<-1<<endl;
        return 0; 
    }
    cout<<accumulate(dis+1,dis+1+n,0LL)<<endl;//注意答案可能会爆 int
    return 0;
}

5.2 P2294 [HNOI2005]狡猾的商人

本题需要自己构造约束条件，但是思维难度也比较简单。

显然，判断账单真假就是问存不存在一组 a_i 满足题目所给的约束条件。然而，题目中给的条件是一段 a_i 的和，于是我们可以用 S_i 表示前缀和。记 a_u 到 a_v 的和为 w，得到：

\sum^v_{i=u}a_i=S_v-S_{u-1}=w

于是约束条件就转化为 S_v-S_{u-1}\le w 并且 S_u-S_{v-1}\ge w。用上述变形即可求解。

\begin{cases}S_v\le S_{u-1}+w\\S_{v-1}\le S_{u}-w\end{cases}

剩下的就是差分约束模板了。判负环即可。

另外，由于题目只要求我们判负环，因此我们可以不新建超级源点，只将所有连通图遍历一遍。对于入队次数为 0 的节点，就作为起点进行 SPFA，以保证遍历整个图。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;

const int MAXN=3e5+5;
int n,m,st;
struct node
{
    int to,val;
};
vector<node> edge[MAXN];
bool visit[MAXN];
int dis[MAXN],cnt[MAXN];

void clear(void)//别忘了多测要清空
{
    memset(dis,0x3f,sizeof(dis));
    memset(visit,false,sizeof(visit));
    memset(cnt,0,sizeof(cnt));
    for(int i=0;i<=n*2;i++) edge[i].clear();
}

bool solve(int s)
{
    queue<int> q;q.push(s);
    dis[s]=0;visit[s]=true;
    while(!q.empty())
    {
        const int u=q.front();
        q.pop();
        visit[u]=false;
        for(auto it:edge[u])
        {
            const int v=it.to,w=it.val;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if(!visit[v])
                {
                    visit[v]=true;
                    q.push(v);
                    cnt[v]++;
                    if(cnt[v]>=n+1)//判负环
                     return false;
                }
            }
        }
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    int T;cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=1;i<=m;i++)
        {
            int u,v,w;cin>>u>>v>>w;
            edge[v].push_back(node{u-1,-w});
            edge[u-1].push_back(node{v,w});
        }
        bool f=true;
        for(int i=0;i<=n && f;i++)//对于每个连通图都判一遍
         if(!cnt[i] && !solve(i))
           f=false;
        puts(!f?"false":"true");
        clear();
    }
    return 0;
}

6. 参考资料