差分约束两大问题简单证明

差分约束两大问题简单证明
差分约束的两个问题

差分约束的两个问题

求不等式组的可行解

差分约束与最短路径

这个图中就给出了如何将不等式组问题转换成最短路径问题,这个问题最关键在于在求解单源最短路径的过程中会使得所有边满足三角不等式:
dist(i)dist(j)+ckdist(i) \leq dist(j) + c_{k}

因此:

源点需要满足的条件:从源点出发,一定可以走到所有的边(这个是很重要的)

步骤:

  1. 先将每个不等式 xixj+ckx_{i} \leq x_{j} + c_{k} , 转化成一条从 xjx_{j} 走到 xix_{i}, 长度为 ckc_{k} 的一条边
  2. 找到一个超级源点,使得该源点一定可以遍历到所有边
  3. 从源点求一遍单源最短路

无解证明:
这个地方有个点,就是如果图中存在负环的话,那么不等式组就是无解的,因为:

差分约束无解证明

图中证明很清晰,所以如果存在负环的话就是无解,这个是针对小于等于不等式组而言,同理的,如果对于大于等于的不等式组而言,如果存在正环的话,就是无解

因此这个问题的结果就只有两种情况:

  • 结果1:如果存在负环,则原不等式组一定无解
  • 结果2:如果没有负环,则 dist[i]dist[i] 就是原不等式组的一个可行解

如何求最大值或者最小值

结论:
如果求的是最小值,那么应该求最长路;如果求的是最大值,那么应该求最短路

一般情况下求解最值问题中应该有 xi>=cx_{i} >= c 这样的不等式约束,否则是可以不断加常数的,不等式组不存在最大值或者最小值,那么问题来了, 如何转换 xi>=cx_{i} >= c 呢?

问题1:如何转换 xi>=cx_{i} >= c, 其中 cc 是一个常数,这类的不等式? 方法:只需要建立一个超级源点, 0, 然后建立 0i0 \rightarrow i , 长度是 cc 的边即可

那么上面的结论应该如何解释呢?

以求解最大值为例:
我们先看一下对于某个元素 xix_{i} 而言, 其某个上界是什么,比如对于 xixj+ckxk+c1+c2+...0+c1+c2+...x_{i} \leq x_{j} + c_{k} \leq x_{k} + c_{1} + c_{2} + … \leq 0 + c_{1} + c_{2} + …

那么这个不等式对 xix_{i} 上界的贡献就是后面的那个和 (c1+c2+c3+...)(c_{1} + c_{2} + c_{3} + …) ,其实也就是当前点 xix_{i} 到超级源点的距离,那么如果有多个这样的限制:

  • xiAx_{i} \leq A
  • xiBx_{i} \leq B
  • xiCx_{i} \leq C

显然的,这个 xix_{i} 的最大值就是 Min(A,B,C,...)Min(A, B, C, …)

而又由上面的,这些 A,B,CA, B, C 等价于到源点的路径长度,那么所有的这些约束,也就是所有的这些路径,他们都会有一个长度,这些长度的最小值也就是这个 xix_{i} 的最大值,同样的就是从超级源点出发到达 xix_{i} 的最短路径长度

总结一下方法:以求解 xix_{i} 的最大值为例, 求所有从 xix_{i} 出发,构成的不等式链 xixj+c1xk+c2+c1...c1+c2+...x_{i} \leq x_{j} + c_{1} \leq x_{k} + c_{2} + c_{1} \leq … \leq c_{1} + c_{2} + … 所计算出的上界,最终 xix_{i} 的最大值等于所有上界的最小值

其实不难发现,每一个这样的不等式链都是从源点出发的一条路径

题目

1169. 糖果

幼儿园里有 N 个小朋友,老师现在想要给这些小朋友们分配糖果,要求每个小朋友都要分到糖果。

但是小朋友们也有嫉妒心,总是会提出一些要求,比如小明不希望小红分到的糖果比他的多,于是在分配糖果的时候, 老师需要满足小朋友们的 K 个要求。

幼儿园的糖果总是有限的,老师想知道他至少需要准备多少个糖果,才能使得每个小朋友都能够分到糖果,并且满足小朋友们所有的要求。

输入格式 输入的第一行是两个整数 N,K。

接下来 K 行,表示分配糖果时需要满足的关系,每行 3 个数字 X,A,B。

  • 如果 X=1X=1.表示第 AA 个小朋友分到的糖果必须和第 BB 个小朋友分到的糖果一样多。
  • 如果 X=2X=2,表示第 AA 个小朋友分到的糖果必须少于第 BB 个小朋友分到的糖果。
  • 如果 X=3X=3,表示第 AA 个小朋友分到的糖果必须不少于第 BB 个小朋友分到的糖果。
  • 如果 X=4X=4,表示第 AA 个小朋友分到的糖果必须多于第 BB 个小朋友分到的糖果。
  • 如果 X=5X=5,表示第 AA 个小朋友分到的糖果必须不多于第 BB 个小朋友分到的糖果。

小朋友编号从 11NN

输出格式
输出一行,表示老师至少需要准备的糖果数,如果不能满足小朋友们的所有要求,就输出 1−1

数据范围
1N<1051≤N<105
1K1051≤K≤105
1X51≤X≤5
1A,BN1≤A,B≤N

输入样例

5 7 1 1 2 2 3 2 4 4 1 3 4 5 5 4 5 2 3 5 4 5 1

输出样例

11

分析:
差分约束最值问题模板题目,注意的就是挖掘那个确定的不等式,也是就是题目中所说到的要求每个小朋友都要分到糖果,因此建立从源点到每个点的边权为 11

队列 spfaspfa 会超时,改为 栈 spfaspfa 即可

AC代码:

#include <bits/stdc++.h> using namespace std; using ll = long long; inline int sd(int &n) { return scanf("%d", &n); } inline int sld(ll &n) { return scanf("%lld", &n); } const int inf = 0x3f3f3f3f; const int maxn = 1e6 + 6; int n, m; int h[maxn], e[maxn], w[maxn], ne[maxn], idx; void add(int a, int b, int c){ e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; } int d[maxn]; bool st[maxn]; stack<int > q; int cnt[maxn]; bool spfa(int s){ memset(d, -0x3f, sizeof d); d[s] = 0; q.push(s); while(q.size()){ int x = q.top(); q.pop(); st[x] = false; for(int i = h[x];~i;i = ne[i]){ int y = e[i]; if(d[x] + w[i] > d[y]) { d[y] = d[x] + w[i]; cnt[y] = cnt[x] + 1; if(cnt[y] >= n + 1) return false; if(!st[y]){ st[y] = true; q.push(y); } } } } return true; } int main(){ memset(h, -1, sizeof h); sd(n), sd(m); for(int i = 0;i < m;++i){ int x, a, b; sd(x), sd(a), sd(b); if(x == 1) add(a, b, 0), add(b, a, 0); else if(x == 2) add(a, b, 1); else if(x == 3) add(b, a, 0); else if(x == 4) add(b, a, 1); else add(a, b, 0); } for(int i = 1;i <= n;++i) add(0, i, 1); if(!spfa(0)) puts("-1"); else { ll res = 0; for(int i = 1;i <= n;++i) res += d[i]; cout << res << endl; } return 0; }

0

发表评论

电子邮件地址不会被公开。 必填项已用*标注

6 + 15 =