差分约束学习笔记

傅天宇 · 2020-07-10 22:52:14 · 个人记录

差分约束（Difference-Constraints）

引出差分约束

当我们遇到一个不等式组，比如下面这个

怎么进行求解？

我们可以很容易地想到：

给其中一个变量赋一个具体的值，然后再逐渐估测其他变量的值，并不断修改。

比如：

1.先给 x_{1} 任意赋一个值，比如令 x_{1}=0，之后根据 x_{1}-x_{3} \leq 5 ,x_{1}-x_{2} \leq 2 ，令 x_3=-5,x_2=-2，又因为 x_{2}-x_{1} \leq 0,x_{3}-x_{1} \leq -2，发现这组解满足条件。

2.根据 x_{2}-x_{3} \leq 2，x_3 改为 -4。

3.发现 x_{3}-x_{2} \leq-1 也满足条件

4.解得，x_1=0,x_2=-1,x_3=-4 为其中一组解。

然鹅，这样的方法只适合于规模较小的时候，而且是在猜的基础上的，这样也没有办法来解出题目。

我们观察下这些不等式，像在最短路里的三角不等式，于是，发现了这些性质：

我们设 dis 数组代表长度，跟最短路里的 dis 概念一样。

所以，我们只要对于每个不等式 x_i-x_j \leq y，连一条从 j 到 i 长度为 y 的边，跑一遍最短路，即可得到一组解。备注：我们设 cnt 数组来表示这个点记录了几次，如果这个图有负环，说明 cnt_i \geq n，则要输出无解。这就是差分约束算法的重要思想。

用 SPFA 跑，不能用 dijkstra。

这个是模板。

int dis[5005],cnt[5005];
bool vis[5005];
queue<int>q;
bool SPFA(int s)
{
    dis[s]=0;
    vis[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=fir[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].val)
            {
                dis[v]=dis[u]+e[i].val;
                cnt[v]++;
                if(cnt[v]==n)
                    return 0;
                if(vis[v]==0)
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return 1;
}

寻找可行解

例题

因此对于这类不等式组的求解，我们可以将其抽象成一个有 n 个点的最短路问题，对于不等式 x_i-x_j \leq y，建一条从 j 连向 i 边权为 y 的单向边。

补充： 如果存在符号相反的不等式，如 x_i-x_j \geq y，我们可以通过给两边乘 -1 的方式使其变号，变为 x_j-x_i \leq -y。

建完图后，为了每个点的可达性，我们要新建一个超级源点 s=n+1 向每个点连出一条边权为 0 的边。

于是就很容易地做出来这模板题了。

#include<iostream>
#include<cstdio>
#include<string.h>
#include<queue>
using namespace std;
int n,m,fir[5005],tot;
struct edge
{
    int nxt,to,val;
}e[10005];
void add(int u,int v,int w)
{
    e[++tot]={fir[u],v,w};fir[u]=tot;
}

SPFA

int main()
{
    scanf("%d%d",&n,&m);
    int s=n+1;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(v,u,w);
    }
    for(int i=1;i<=n;i++)
        add(s,i,0);
    memset(dis,0x3f,sizeof dis);
    if(!SPFA(s))
    {
        cout<<"NO";
        return 0;
    }
    for(int i=1;i<=n;i++)
        cout<<dis[i]<<" ";
    return 0;
}

寻找最大解/最小解

最大解：

就是上面那个求法，所以我不再多加述

最小解：

要使所有的 x_i 都尽可能小且大于等于某一个常量 k，就要把求解最短路更换为求解最长路。

与上面的类似

补充： 如果存在符号相反的不等式，如 x_i-x_j \leq y，我们可以通过给两边乘 -1 的方式使其变号，变为 x_j-x_i \geq -y。

注意：求解最小解的图中，因为不存在正环，所以存在最长路。

无解/无穷解

无解：

比如当同时出现 x_i-x_j \leq 2 和 x_j-x_i \leq 1 这两组限制时，就会出现无解的情况，在图中表现为：

• 求最短路时出现负环
• 求最长路时出现正环

代码之前已经放过了 qwq。

无穷解

当所取源点无法到达某一点 t 时，说明 x_t 未被加以限制，此时无论此时 x_t 有无限组解。

比如当同时出现 x_1-x_3 \leq 2 和 x_3-x_1 \leq 1 这两组限制时，x_2 就会出现无穷解的情况

例题

P3275 [SCOI2011]糖果

记小朋友 i 得到的糖果数为 x_i，则 5 种要求对应以下不等式：

则题目求的就是满足这些不等式，且所有 x_i \geq 0，并求 x_i 最小的解。 直接套用差分约束模板，注意求的是最小解。

#include<iostream>
#include<cstdio>
#include<queue>
#include<string.h>
using namespace std;
int n,k,dis[300005],cnt[300005];
int fir[300005],tot;
long long ans;
struct edge
{
    int nxt,to,val;
}e[300005];
int read()
{
    int a=0;
    char x=getchar();
    while(x<'0'||x>'9') x=getchar();
    while(x>='0'&&x<='9') a=(a<<3)+(a<<1)+x-48,x=getchar();
    return a;
}
void add(int u,int v,int w)
{
    e[++tot]={fir[u],v,w};fir[u]=tot;
}
bool vis[300005],flag;
queue<int>q;
bool SPFA(int s)
{
    dis[s]=0;
    vis[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=fir[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(dis[v]<dis[u]+e[i].val)
            {
                dis[v]=dis[u]+e[i].val;
                cnt[v]++;
                if(cnt[v]>=n)
                {
                    cout<<-1;
                    return 0;
                }
                if(vis[v]==0)
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return 1;
}
int main()
{
    n=read();k=read();
    int s=n+1;
    while(k--)
    {
        int opt,u,v;
        opt=read();u=read();v=read();
        if(opt==1) add(u,v,0),add(v,u,0);
        else if(opt==2) add(u,v,1);
        else if(opt==3) add(v,u,0);
        else if(opt==4) add(v,u,1);
        else add(u,v,0);
        if((u==v)&&(opt==2||opt==4))
        {
            cout<<-1;
            return 0;
        }
    }
    for(int i=n;i>=1;i--) add(s,i,1);
    if(!SPFA(s)) return 0;
    for(int i=1;i<=n;i++)
        ans+=dis[i];
    cout<<ans;
    return 0;
}

注意：

加边的时候是要倒着加，从 n 到 1，因为有一个 duliu 数据是一条链，如果正着加边会 T。