【学习笔记】差分约束

图论与不等式的完美结合 。

• 如果求的是两个变量差的最大值，那么求最短路，形如 $x_i+d\ge x_j$
• 如果求的是两个变量差的最小值，那么求最长路，形如 $x_i+d\le x_j$

瞎讲几道吧

Wannafly 挑战赛9E - 组一组

有一个长为 n 的数列 A，其中有 m 个限制条件，条件有两种：

1、对于区间 [l,r]，其区间元素按位或和等于 x。
2、对于区间 [l,r]，其区间元素按位与和等于 x。

求出一个数列 A，使得满足给定的 m 个条件，保证有解。

1<=n,m<=10^5, 1<=l<=r<=n, 0<=x<2^20

sol：显然按位考虑 。然后求最短路 。

等等 … 直接 spfa 太慢会 T 。

我们可以把上界再控制小一点。

对于或为 0 的运算，我们知道 s[l~r]=0 。

对于前缀和 sum[i] ，假设 s[1~i] 有 x 个 0 。那么 sum[i]<=i-x 。

我们直接从源点连一条 i-x 的边 ，能有效减少迭代次数 。

[POI2015] PUS

POI

首先不考虑复杂度问题，这是一道差分约束 。

然后考虑优化一下。

其一是建图的时候，边的数量过多的问题，我们使用线段树来优化建图。

其二则是数据太大最短路跑不过的问题。我们 根据图的特殊性来优化 。

首先是 d[i]=x ，我们扔掉负边，即只保留下界，最后回头检验。

这样都是正边了。

其次如果有正环，输出无解 。

直接 DAG 跑拓扑排序即可。