【题解】洛谷 P5960 【模板】差分约束算法

wsyhb

2020-08-01 23:21:21

题解

前言

最近刷题时，偶然做到一道差分约束的简单题。明明以前学过差分约束，却怎么写都写不对。回过头来发现差分约束的模板题都没过，费了好大劲才解决。

为了不让其他学习差分约束的 OIer 们跟我犯同样的错误，我特地写下这篇题解，讲解了一下基本的算法思路，整理了常见的错误，希望每一个 OIer 都能在这篇题解中有所收获！

另外，如果您在这篇题解中发现任何错误或不当之处，欢迎在评论区指出！

前置知识

在阅读这篇题解前，你需要掌握 Bellman-Ford 或 SPFA 求解单源最短路径。

（模板：P3371 【模板】单源最短路径（弱化版））

定义

如果一个系统由 n 个变量 a_1,a_2,\cdots,a_n 和 m 个约束条件组成，每个约束条件均为形如 a_i-a_j \leq k 的不等式（i,j \in [1,n]，k 为常数），则称其为差分约束系统。

换句话说，差分约束系统是求解关于一组变量的特殊不等式组的方法。

（以上内容摘编自百度百科）

算法详解

看到这个不等式，或许你会有点懵，我们先简单变个形：

\because a_i-a_j \leq k \quad \therefore a_i \leq a_j + k

或许您会觉得我在侮辱您的智商，不过请继续看下去：

现在将 m 个约束条件分成 n 组，a_i \leq a_j+k 属于第 i 组。

单独考虑第 i 组，设第 i 组共有 x 个条件，每个条件的 j 依次等于 b_1,b_2,\cdots,b_x，每个条件的 k 依次等于 c_1,c_2,\cdots,c_x。（即这 x 个条件分别为 a_i \leq a_{b_{_1}}+c_1，\cdots，a_i \leq a_{b_{_x}}+c_x）

那么第 i 组条件就等价于：

a_i \leq min\{a_{b_{_1}}+c_1,\cdots,a_{b_{_x}}+c_x\}

考虑

a_i = min\{a_{b_{_1}}+c_1,\cdots,a_{b_{_x}}+c_x\}

我们突然发现这是一个最短路的形式 -- 具体来说，b_j 向 i 连一条长度为 c_j 的边，a_i 为源点到 i 的最短路径距离，那么上述等式就相当于用点 b_j 去更新 i。（j \in \{1,2,\cdots,x\}）

我们回到一开始的式子 a_i \leq a_j+k，根据上述分析，我们可以将其转化为从 j 到 i 的一条长度为 k 的边，那么 a_i 就转化成了源点到 i 的最短路径距离。

上述不等式组显然有可能无解，那么怎么判定无解呢？

由于 a_i 是一组最短路的解，那么只需判定最短路是否无解即可。

什么，你不知道如何判定最短路无解？

当然是判负环呀！

具体来说，如果不存在负环，Bellman-Ford 在 n 次松弛后就该结束了，所以只需要再尝试松弛一次，如果多的这一次松弛成功，说明有负环，无解；否则有解。

再说说 SPFA 判负环，道理其实是一样的。你每次将一个点丢进队列里，相当于是对这一个点的所有出边进行松弛，那么只需要记录每个点的进队次数，若超过 n，说明松弛次数太多，有负环，无解；否则有解。

另外一种思路

在一开始的推导中，我们将 a_i 移到了等式的一边，现在我们尝试将 a_j 移到等式的一边：

\because a_i-a_j \leq k \quad \therefore a_j \geq a_i - k

与一开始的推导同理可得，从 i 到 j 连一条长度为 -k 的边，a_i 即为源点到 i 的最长路径距离。

那么只需要以此跑最长路，并判断正环即可。

注：读者可以尝试按照一开始的推导演算一遍，加深理解。

易错点

这里是重点，不少题解都没有详细讲解这两点，初学差分约束是很有可能踩雷的！

1.用错算法

由于 k 符号不确定，所以可能有负（正）权边，这也是为什么我们不能使用 dijkstra 算法，而只能使用 Bellman-Ford 或 SPFA 求最短（长）路的原因。

dijkstra 算法求最短（长）路为何不能用于负（正）权边

（如果您早就明白这是为什么，请自行跳过）

以求最短路为例，dijkstra 算法是利用贪心思想，每次用距离源点最近的、未讨论过的点去更新其他点的最短距离，有点类似于 bfs （宽度优先搜索）。

但当出现负权边时，后面讨论的点相较于已讨论的点，可能会距离源点更近，导致已讨论的点会被更新，却不会再次拿来讨论，此时 O(n^2) 的 dijkstra 算法就失效了。

不过，如果使用带有堆优化的时间复杂度为 O(nlog_{_2}m) 的 dijkstra 算法，它会退化成 SPFA 算法，相当于将 SPFA 算法中的队列换成堆，时间复杂度为 O(nmlog_{_2}m)，显然超时。

最后放一个例子，以便读者理解：

以 1 为源点，用 O(n^2) 的 dijkstra 算法求解单源最短路，所求得的 dis_{_4} 为 7，即路径 1 -> 2 -> 4。而实际上 dis_{_4} 应该为 6，即路径 1 -> 3 -> 5 -> 2 -> 4。

错误原因是 dis_{_2}=3<dis_{_3}=5，所以先讨论了点 2 ，将点 4 更新，而之后点 5 去更新点 2，点 2 却不会再用新的 dis_{_2}=2 去更新点 4 了。

2.图不连通

这里可能会存在点之间既不直接约束也不间接约束的情况，在建图上的体现就是图不连通。

举个简单的例子：（n=5，m=3）

x_2-x_1 \leq 5\\ x_5-x_4 \leq 3\\ x_1-x_3 \leq 4\\ \end{cases}

依据第一种思路建图如下：

此时无论以 1 , 2 , 3 , 4 , 5 哪个点作为源点，都无法计算出正确答案。（对于 SPFA）

理由是以其中一个点作为源点，只能计算出这个点所在连通块的答案，并没有计算其他连通块的答案。

解决方案

一、SPFA

一开始将所有点放入队列中而不是只放一个起点，这样每个点都被作为起点讨论过。
建一个虚拟源点 0，从这个虚拟源点向其他所有点都连一条长度为 0 的边，以虚拟源点为起点放入队列，这样的效果与前一种完全相同。

二、Bellman-Ford

无需操作，算出来的答案本来就是正确的。

因为每次松弛是对所有边进行操作，不会出现只计算一个连通块的情况。

代码

两种思路、两种算法（SPFA 及 Bellman-Ford）、两种解决方案，都在下方代码有所体现！

第一种思路（求最短路）+ SPFA + 解决方案1（全部点放入队列）

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=5e3+5;//点数
const int M=5e3+5;//边数 
int End[M],Last[N],Next[M],Len[M],e;//链式前向星
void add_edge(int x,int y,int z)
{
    End[++e]=y;
    Next[e]=Last[x];
    Last[x]=e;
    Len[e]=z;
}
int dis[N],cnt[N];//cnt记录各个点入队次数 
queue<int> q;
bool inq[N];//inq标记各个点是否在队列中 
bool spfa(int s)
{
    for(int i=1;i<=n;i++) dis[i]=1e9;//最短路，初始值为inf
    dis[s]=0;
    for(int i=1;i<=n;i++)//全部放入队列
    {
        q.push(i);
        inq[i]=true;
        cnt[i]++;
    }
    while(q.size())
    {
        int x=q.front();
        q.pop();
        inq[x]=false;
        for(int i=Last[x];i;i=Next[i])
        {
            int y=End[i];
            if(dis[y]>dis[x]+Len[i])
            {
                dis[y]=dis[x]+Len[i];
                if(!inq[y])
                {
                    q.push(y);
                    inq[y]=true;
                    cnt[y]++;
                    if(cnt[y]>n+1) return false;//返回 false，意味着无解
                }
            }
        }
    }
    return true;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add_edge(y,x,z);
    }
    if(spfa(1))
    {
        for(int i=1;i<=n;i++) printf("%d%c",dis[i],i<n?' ':'\n');
    }
    else printf("NO\n");
    return 0;
}

第二种思路（求最长路）+ SPFA + 解决方案2（虚拟源点）

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=5e3+5;//点数 
const int M=1e4+5;//边数，注意虚拟源点连的边 
int End[M],Last[N],Next[M],Len[M],e;//链式前向星 
void add_edge(int x,int y,int z) 
{
    End[++e]=y;
    Next[e]=Last[x];
    Last[x]=e;
    Len[e]=z;
}
int dis[N],cnt[N];//cnt记录各个点入队次数 
queue<int> q;
bool inq[N];//inq标记各个点是否在队列中 
bool spfa(int s)
{
    for(int i=0;i<=n;i++) dis[i]=-1e9;//最长路，初始值为-inf
    dis[s]=0;
    q.push(s);
    inq[s]=true;
    cnt[s]++;
    while(q.size())
    {
        int x=q.front();
        q.pop();
        inq[x]=false;
        for(int i=Last[x];i;i=Next[i])
        {
            int y=End[i];
            if(dis[y]<dis[x]+Len[i])
            {
                dis[y]=dis[x]+Len[i];
                if(!inq[y])
                {
                    q.push(y);
                    inq[y]=true;
                    cnt[y]++;
                    if(cnt[y]>n+1) return false;//返回 false，意味着无解 
                }
            }
        }
    }
    return true;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) add_edge(0,i,0);//虚拟源点连边 
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add_edge(x,y,-z);
    }
    if(spfa(0))
    {
        for(int i=1;i<=n;i++) printf("%d%c",dis[i],i<n?' ':'\n');
    }
    else printf("NO\n");
    return 0;
}

第一种思路 + Bellman-Ford

#include<bits/stdc++.h>
#define min(a,b) ((a)<(b)?(a):(b)) 
using namespace std;
int n,m;
const int N=5e3+5;//点数 
const int M=5e3+5;//边数 
struct edge
{
    int x,y,z;
}e[M];//存边 
int dis[N];
bool Bellman_Ford(int s)
{
    for(int i=1;i<=n;i++) dis[i]=1e9;
    dis[s]=0;
    for(int t=1;t<=n;t++)
        for(int i=1;i<=m;i++)
            dis[e[i].y]=min(dis[e[i].y],dis[e[i].x]+e[i].z);
    for(int i=1;i<=m;i++)
        if(dis[e[i].x]+e[i].z<dis[e[i].y]) return false;//返回 false，意味着无解 
    return true;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].y,&e[i].x,&e[i].z);
    if(Bellman_Ford(1))
    {
        for(int i=1;i<=n;i++) printf("%d%c",dis[i],i<n?' ':'\n');
    }
    else printf("NO\n");
    return 0;
}

【题解】洛谷 P5960 【模板】差分约束算法

题解

目录

前言

前置知识

定义

算法详解

易错点

1.用错算法

2.图不连通

代码