差分约束

__Green_tick__ · 2024-11-09 12:14:26 · 算法·理论

差分约束

前置知识

多元一次不等式组

经典例题

P5960 【模板】差分约束
P1993 小 K 的农场

算法作用

求多元一次不等式组的一组或多组解。

如下，是一个多元一次不等式组：

\begin{cases} x_{c_1}-x_{c'_1}\leq y_1 \\x_{c_2}-x_{c'_2} \leq y_2 \\ \cdots\\ x_{c_m} - x_{c'_m}\leq y_m\end{cases}

也是差分约束的一般形式。

算法定义

差分约束系统 是一种特殊的 n 元一次不等式组，它包含 n 个变量 x_1,x_2,\dots,x_n 以及 m 个约束条件，每个约束条件是由两个其中的变量做差构成的，形如 x_i-x_j\leq c_k ，其中 1 \leq i, j \leq n , i \neq j , 1 \leq k \leq m 并且 c_k 是常数（可以是非负数，也可以是负数）。我们要解决的问题是：求一组解 x_1=a_1,x_2=a_2,\dots,x_n=a_n ，使得所有的约束条件得到满足，否则判断出无解。

差分约束系统中的每个约束条件 x_i-x_j\leq c_k 都可以变形成 x_i\leq x_j+c_k ，这与单源最短路中的三角形不等式 dist[y]\leq dist[x]+z 非常相似。因此，我们可以把每个变量 x_i 看做图中的一个结点，对于每个约束条件 x_i-x_j\leq c_k ，从结点 j 向结点 i 连一条长度为 c_k 的有向边。

注意到，如果 \{a_1,a_2,\dots,a_n\} 是该差分约束系统的一组解，那么对于任意的常数 d，\{a_1+d,a_2+d,\dots,a_n+d\} 显然也是该差分约束系统的一组解，因为这样做差后 d 刚好被消掉。

算法步骤

设 dist[0]=0 并向每一个点连一条权重为 0 边，跑单源最短路，若图中存在负环，则给定的差分约束系统无解，否则， x_i=dist[i] 为该差分约束系统的一组解。

算法性质

一般使用 Bellman–Ford 或队列优化的 Bellman–Ford（俗称 SPFA，在某些随机图跑得很快）判断图中是否存在负环，最坏时间复杂度为 O(nm) 。

P5960 【模板】差分约束

正确代码

#include<bits/stdc++.h>
using namespace std;
/*Optimization series
#pragma GCC/G++ optimize(1)
#pragma GCC/G++ optimize(2)
#pragma GCC/G++ optimize(3,"OSumast","inline")
*/
const long long MaxN=5e3+10; 
long long dis[MaxN]; 
long long num[MaxN];
bool vis[MaxN];
long long elast[MaxN];
queue<long long> que;
long long n,m,cnt;
struct Edge{
    long long next;
    long long len;
    long long to;
}edge[MaxN*2];

void Add_Edge(long long u,long long v,long long y){//加边：u -> v 权值为 y
    cnt++;
    edge[cnt].to=v;
    edge[cnt].len=y;
    edge[cnt].next=elast[u];
    elast[u]=cnt;
    return;
}

bool SPFA(long long start){
    for(long long i=1;i<=n;i++){
        dis[i]=INT_MAX;
        vis[i]=false;
    }
    dis[start]=0;
    vis[start]=true;
    que.push(start);
    num[start]++;  
    while(que.size()){
        long long u=que.front();
        que.pop();
        vis[u]=false;
        for(long long i=elast[u];i;i=edge[i].next){
            if(dis[edge[i].to]>dis[u]+edge[i].len){
                dis[edge[i].to]=dis[u]+edge[i].len;
                if(num[edge[i].to]>=n){
                    return false;//出现负环即无解
                }
                if(vis[edge[i].to]==false){
                    que.push(edge[i].to);
                    num[edge[i].to]++;
                    vis[edge[i].to]=true;
                }
            }
        }
    }
    return true;
}

int main(){
    cin>>n>>m;
    for(long long i=1;i<=n;i++){
        Add_Edge(0,i,0);//建立虚拟源点及其边
    }
    for(long long i=1;i<=m;i++){
        long long u,v,y;
        cin>>u>>v>>y;
        Add_Edge(u,v,y);//建边
    }
    if(!SPFA(0)) cout<<"NO"<<endl;//无解（出现负环）
    else{
        for(long long i=1;i<=n;i++){
            cout<<dis[i]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

例题 P1993 小 K 的农场

题目大意

求解差分约束系统，有 m 条约束条件，每条都为形如 x_a-x_b\geq c_k ， x_a-x_b\leq c_k 或 x_a=x_b 的形式，判断该差分约束系统有没有解。

思路讲解

令 opt=a,u=b,v=c。

先读入一个 opt。

按照题意：

农场 a 比农场 b 至少多种植了 c 个单位的作物；

农场 a 比农场 b 至多多种植了 c 个单位的作物；

农场 a 与农场 b 种植的作物数一样多。

当 opt=1 时：

加入边 u 到 v 的边权值为 -y；

当 opt=2 时：

加入边 v 到 u 的边权值为 y；

当 opt=3 时：

加入边 u 到 v 的边权值为 0；
加入边 v 到 u 的边权值为 0。

则有如下代码：

if(opt==1){
  long long u,v,y;
  cin>>u>>v>>y;
  Add_Edge(u,v,-y);
}else if(opt==2){
  long long u,v,y;
  cin>>u>>v>>y;
  Add_Edge(v,u,y);
}else{
  long long u,v;
  cin>>u>>v;
  Add_Edge(v,u,0);
  Add_Edge(u,v,0);
}

正确代码

#include<bits/stdc++.h>
using namespace std;
/*Optimization series
#pragma GCC/G++ optimize(1)
#pragma GCC/G++ optimize(2)
#pragma GCC/G++ optimize(3,"OSumast","inline")
*/
const long long MaxN=5e3+10; 
long long dis[MaxN]; 
long long num[MaxN];
bool vis[MaxN];
long long elast[MaxN];
queue<long long> que;
long long n,m,cnt;
struct Edge{
    long long next;
    long long len;
    long long to;
}edge[MaxN*2];

void Add_Edge(long long u,long long v,long long y){
    cnt++;
    edge[cnt].to=v;
    edge[cnt].len=y;
    edge[cnt].next=elast[u];
    elast[u]=cnt;
    return;
}

bool SPFA(long long start){
    for(long long i=1;i<=n;i++){
        dis[i]=INT_MAX;
        vis[i]=false;
    }
    dis[start]=0;
    vis[start]=true;
    que.push(start);
    num[start]++; 
    while(que.size()){
        long long u=que.front();
        que.pop();
        vis[u]=false;
        for(long long i=elast[u];i;i=edge[i].next){
            if(dis[edge[i].to]>dis[u]+edge[i].len){
                dis[edge[i].to]=dis[u]+edge[i].len;
                if(num[edge[i].to]>=n){
                    return false;
                }
                if(vis[edge[i].to]==false){
                    que.push(edge[i].to);
                    num[edge[i].to]++;
                    vis[edge[i].to]=true;
                }
            }
        }
    }
    return true;
}

int main(){
    cin>>n>>m;
    for(long long i=1;i<=n;i++){
        Add_Edge(0,i,0);
    }
    for(long long i=1;i<=m;i++){
        long long opt;
        cin>>opt;
        if(opt==1){
            long long u,v,y;
            cin>>u>>v>>y;
            Add_Edge(u,v,-y);
        }else if(opt==2){
            long long u,v,y;
            cin>>u>>v>>y;
            Add_Edge(v,u,y);
        }else{
            long long u,v;
            cin>>u>>v;
            Add_Edge(v,u,0);
            Add_Edge(u,v,0);
        }
    }
    if(!SPFA(0)) cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
    return 0;
}