您的位置: 首页  >  文章  >  初识差分约束

初识差分约束

分类: 文章 • 2024-01-07 11:21:46

对于差分约束理解

差分约束解决了一类不等式组的解的问题，如

(0)x1−x0≤a x_1 - x_0 \leq a \tag{0}
(1)x2−x1≤b x_2-x1\leq b \tag{1}
(2)x2−x0≤c x_2-x_0\leq c \tag{2}
然后我们需要求的是x2−x0x_2-x_0的最大值MaxMax
经过观察我们可以发现将(0)+(1)(0)+(1)得到
(3)x2−x0≤a+b\color{red} x_2-x_0 \leq a+b \tag{3}
(2)x2−x0≤cx_2-x_0 \leq c \tag{2}
综上
Max=min{a+b,c}Max = min\{ a+b,c\}
如果我们用几何的方式来表示这三个不等式的话我们会有新的发现
初识差分约束
Max=min{a+b,c}Max = min\{ a+b,c\}不就是从00到11的最短距离吗
综上我们可以得出差分约束的一种解法-利用最短路算法

差分约束系统与最短路算法

现在我们将目光放在如何构造差分约束系统，并使用最短路算法解决。
对于任意不等式组
x1−x0≤ax2−x1≤bx2−x0≤c x_1 - x_0 \leq a \\ x_2-x1\leq b \\ x_2-x_0\leq c
将其写成如下形式
xi−xj≤aix_i-x_j \leq a_i
并对每一个不等式建立有向边j→ij\rightarrow i边权为aia_i
求xu−xvx_u - x_v的最大值 =>=>即求v→uv\rightarrow u的最短路径

最大值与最小值的转换

当我们需要求的是xu−xvx_u - x_v的最小值的时候该怎么办
xu−xv≥Min x_u-x_v \geq Min
需要将差分约束系统所有不等式组变为
xj−xi≥−aix_j-x_i \geq -a_i
并对每一个不等式建立有向边i→ji\rightarrow j边权为−ai-a_i
求xu−xvx_u - x_v的最小值=>=>求v→uv\rightarrow u的最长路径
这种方法和上述最短路法是等价的

最短路算法SPFA

由于差分约束系统用存在负权边，传统的最短贪心策略Dijkstra算法并不能处理负权边。
再者由于负权边会出现负权环，SPFA算法可以对负权图进行判断。
SPFA算法的原理：利用队列不断从队列中选取出结点出来松弛，直到队列为空为止。
基本模板

bool SPFA(int from,int to) {
    memset(vis,0,sizeof(vis));
    memset(cnt,0,sizeof(cnt));
    for(int i=0;i<maxn;i++) dist[i] = inf;
    vis[from] = true;
    dist[from] = 0;
    queue<int> qu;
    qu.push(from);
    cnt[from]=1;
    while(!qu.empty()) {
        int u = qu.front();qu.pop();
        vis[u] = false;
        for(int i=head[u];~i;i=edge[i].next) {
            int v = edge[i].v;
            if(dist[v] > dist[u] + edge[i].cost) {
                dist[v] = dist[u] + edge[i].cost;
                if(!vis[v]) {
                    vis[v] = true;
                    qu.push(v);
                    if(++cnt[v]>n) return false;
                }
            }
        }
    }
    return true;
}

vis[]vis[]表示结点是否在队列中
dist[]dist[]记录了源点到其他点的最短路径
cnt[]cnt[]用于判断是否存在负权环，当一个结点进入队列超过nn次，即存在负权环

例题

例题1：ZOJ 2770

题意
给出nn个点表示nn个军营，CiC_i表示第i个军营可容纳的士兵的最大值，接着给出mm条边(i,j,k)(i,j,k)表示从第ii到第jj个军营拥有的最少士兵数。求在满足以上条件下最少有多少士兵
题解
差分系统
设每个军营人数为AiA_i,军营容量为CiC_i,军营人数的前缀和为SnS_n

  1. Ai≤CiAi \leq Ci 写成前缀和的形式
    Si−Si−1&lt;=CiS_i - S_{i-1} &lt;= C_i

  2. 从第ii个军营到第jj个军营的人数和至少为kk
    Sj−Si−1≥kS_j - S_{i-1} \geq k 转换为
    Si−1−Sj≤−k S_{i-1} - S_j \leq -k

  3. 每个军营都必须有人Ai≥0A_i \geq 0
    Si−Si−1≥0 S_i - S_{i-1} \geq 0 转换为
    Si−1−Si≤0 S_{i-1} - S_i \leq 0
    目标：求解Sn−S0S_n - S_0的最小值，设最小值为MM
    Sn−S0≥MS_n - S_0 \geq M
    转换
    S0−Sn≤−MS_0 - S_n \leq -M

    于是我们只需要求解从点nn到点00的最短路径−M-M
    去负号即为MM

    注：存在负环则为不可估计无解

综上得到的差分约束系统为
Si−Si−1&lt;=CiSi−1−Sj≤−kSi−1−Si≤0S_i - S_{i-1} &lt;= C_i \\ S_{i-1} - S_j \leq -k \\ S_{i-1} - S_i \leq 0
Target:S0−Sn≤−MTarget:S_0 - S_n \leq -M
代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e3+10;
const int maxm = 1e5+10;
struct Edge {
    int v;
    ll cost;
    int next;
    Edge(){}
    Edge(int _v,ll _c,int _n):v(_v),cost(_c),next(_n){}
};
Edge edge[maxm];
int n,m;
int head[maxn],tot;
bool vis[maxn]; // 是否在队列
int cnt[maxn]; // 每个点的入队次数
ll dist[maxn]; // 最短路径
ll cot[maxn];
inline void addedge(int u,int v,ll val) {
    edge[tot] = Edge(v,val,head[u]);
    head[u] = tot++;
}
bool SPFA(int from,int to) {
    memset(vis,0,sizeof(vis));
    memset(cnt,0,sizeof(cnt));
    for(int i=0;i<maxn;i++) dist[i] = inf;
    vis[from] = true;
    dist[from] = 0;
    queue<int> qu;
    qu.push(from);
    cnt[from]=1;
    while(!qu.empty()) {
        int u = qu.front();qu.pop();
        vis[u] = false;
        for(int i=head[u];~i;i=edge[i].next) {
            int v = edge[i].v;
            if(dist[v] > dist[u] + edge[i].cost) {
                dist[v] = dist[u] + edge[i].cost;
                if(!vis[v]) {
                    vis[v] = true;
                    qu.push(v);
                    if(++cnt[v]>n) return false;
                }
            }
        }
    }
    return true;
}
inline void init() {
    memset(head,-1,sizeof(head));tot = 0;
    memset(cot,0,sizeof(cot));
}

int main()
{
    while(~scanf("%d%d",&n,&m)) {
        init();
        ll cost;
        for(int i=0;i<n;i++) {
            scanf("%lld",&cost);
            cot[i+1] = cot[i] + cost;
            addedge(i,i+1,cost);
            addedge(i+1,i,0);
        }
        for(int i=0,x,y;i<m;i++) {
            scanf("%d%d%lld",&x,&y,&cost);
            addedge(y,x-1,-cost);
            //addedge(x-1,y,cot[y]-cot[x-1]);
        }
        bool flag = SPFA(n,0);
        if(flag) printf("%lld\n",-dist[0]);
        else printf("Bad Estimations\n");
    }
    return 0;
}
例题2：CSP201809-4 再卖菜

相关推荐