差分约束
给出\(n\)个活动，设\(t_i\)表示第\(i\)个活动开始的时间。这些活动满足以下\(m\)个类似关系：
\[\begin{cases} t_{i1}-t_{j1}<=B_1 \\ t_{i2}-t_{j2}<=B_2 \\ \dots \\t_{im}-t_{jm}<=B_m \end{cases} \]其中\(1 <= i_1，i_2，\dots, i_m，j_1，j_2，\dots, j_m<=n\)
求满足这m个不等式的解。
这些活动的约束条件全部为两个活动的开始时间的差值不等式，称这样的问题为差分约束系统。
差分约束系统可以转化为图论的最短路问题。
首先，我们回顾一下，dijkstra算法过程中，有一个松弛不等式。
如果图中存在一条边\((u, v)\), 其边权为\(w\)。
如果存在下列不等式：
\(dis[u] + w < dis[v]\)
则说明\(dis[v]\)能够被更新。
而如果已经求完了最短路，则边\((u,v)\)不能再松弛。
即此时有：
\(dis[u] + w >= dis[v]\)
每条边都会有类似的不等式。如果将每条边的这个不等式联立起来，就可以得到一个不等式方程组。
如果把求完了最短路之后，每个点的dis值，都一定能满足这个不等式方程组。于是我们就可以通过最短路来得到这个不等式方程组的解。
回到最开始的不等式方程组，
\[\begin{cases} t_{i1}-t_{j1}<=B_1 \\ t_{i2}-t_{j2}<=B_2 \\ \dots \\t_{im}-t_{jm}<=B_m \end{cases} \]可以转换为：
\[\begin{cases} t_{j1} + B_1 \geq t_{i1} \\ t_{j2} + B_2 \geq t_{i2} \\ \dots \\t_{jm} + B_m \geq t_{im} \end{cases} \]将\(t\)数组当做\(dis\)数组，\(i1,j1,i2,j2,\dots, im,jm\) 看做点。
对于第一个不等式\(t_{j1} + B_1 \geq t_{i1}\) ，\(j1\)向\(i1\)连边，边权为\(B_1\).
其他不等式类似去连。
举几个例子：
- \(t_i - t_j \leq B1\)
- \(t_i - t_j \leq -B1\)
- \(t_i - t_j \geq B1\)
- \(t_i - t_j \geq -B1\)
对应的连边分别为：
- \(j\)向\(i\)连边，边权为\(B1\)
- \(j\)向\(i\)连边，边权为\(-B1\)
- \(i\)向\(j\)连边，边权为\(-B1\)
- \(i\)向\(j\)连边，边权为\(B1\).
还有可能遇到这样的不等式，\(t_i - t_j \lt B_1\),此处\(B_1\)为整数。
我们可以将它变成\(t_i - t_j \leq B_1 - 1\)， 然后\(j\)向\(i\)连边，边权为\(B_1 - 1\)。
注意：
- 差分约束转换为最短路后，只要最短路有解，则意味着不等式组有无穷多组解。我们一般都会将dis[s]固定为\(0\)，从而得到一组固定的解。
- \(dis[i]\)在图论中是最短距离，但是在原不等式方程组的意义却是最大值，而不是最小值。
例题1：奇怪的数列
题目描述
给出\(3\)个整数\(n,p,q\),寻找\(1\)个由整数组成的数列\((a_1,a_2,\dots,a_n)\)，要求：其中任意连续\(p\)项之和为正数，任意连续\(q\)项之和为负数。 若不存在这样的数列，则输出NO；否则输出满足条件的一个数列即可。
数据范围
\(0<n<100,0<p,q<n\)
分析
对数列求前缀和，sum(k)表示前k个数的和。
这样得到sum(0),sum(1),……sum(n).
根据题意，
sum(k)<sum(k+p)
sum(k)>sum(k+q)
把每一个sum值作为一个顶点，若sum(i)>sum(j),则连一条i指向j的有向边。这样得到一个有向图。若图可以拓扑排序，则有解，否则无解。
若有解，则给sum(0)赋值0，然后按照有向边给其他各点依次赋值，最后求出数列。
比如n=6，p=5，q=3,设sum(k)为前k项之和。
得到如下关系式,
sum0<sum5
Sum1
Sum1>sum4
Sum2>sum5
Sum3>sum6
该图可以进行拓扑排序。
分别为
Sum2,sum5,sum0,sum3,sum6,sum1,sum4
于是令其分别为
2,1,0,-1,-2,-3,-4
推出数列
为-3,5,-3,-3,5,-3
例题2 01序列
题目描述
考虑一个长度为\(N\)由0和1组成的序列，\(A=(A_1,A_2,\dots,A_n)\),满足下列的\(M\)个条件：
每个条件形如：L R X,表示序列的区间\([L,R]\)中至少有\(X\)个1。
输出满足条件的且包含最少的1的序列。如果有多个满足要求的序列，输出字典序最小的序列。
保证 \(1 \leq X_i \leq R_i -L_i + 1\)，可以证明这样的序列一定存在。
分析
用\(dis_i\)表示前\(i\)个数的前缀和，则一个条件\((i,j,k)\),表示\(dis[j]-dis[i-1] >= k\), 则点\(i-1\)向\(j\)连一条边,权值为\(k\).
除此之外，因为\(dis[i - 1] + 1 \geq dis[i] \geq dis[i - 1]\),所以还要从点\(i\)到点\(i-1\)连一条长度为\(0\)的边，从\(i-1\)向\(i\)连一条长度为\(0\)的边。
然后从源点\(0\)开始求最短路。这样求出来的\(dis_i\), 虽然能满足题目不等式，但是它的意义却是包含\(1\)最多的，显然这不符合题意。
我们可以换一个角度，设\(dis_i\)表示前\(i\)个数中包含的\(0\)的个数。
则原条件\((i,j,k)\), 现在的意义应该是\(dis[j] - dis[i-1] <= (j - i + 1 - k)\)，连边也变成了\(i - 1\)向\(j\)连边，边权为\(j - i + 1 - k\). 边权不可能为负。
同时，因为有\(dis[i - 1] \leq dis[i] \leq dis[i - 1] + 1\), 所以，\(i\)向\(i-1\)连边权为\(0\)的边，\(i-1\)向\(i\)连边权为\(1\)的边。
这样，从\(0\)点出发跑dijkstra，可以求出dis数组，从而确定每一个位置的数字是\(0\)还是\(1\)了。
#include <bits/stdc++.h>
using namespace std;
#define maxn 200005
int dis[maxn], ans[maxn];
bool inq[maxn];
struct edge{
int v, w, nxt;
}es[maxn << 2];
struct node{
int v, dis;
node(int a = 0, int b = 0){
v = a, dis = b;
}
bool operator < (const node &t)const {
return dis > t.dis;
}
};
priority_queue<node> myq;
int n, m, ecnt;
int fir[maxn];
void adde(int a, int b, int c){
es[++ecnt].v = b, es[ecnt].w = c, es[ecnt].nxt = fir[a], fir[a] = ecnt;
}
void dijkstra(int s){
dis[s] = 0;
myq.push(node(s, 0));
inq[s] = 1;
while(!myq.empty()){
s = myq.top().v;
myq.pop();
if(inq[s] == 0) continue;
inq[s] = 0;
for(int i = fir[s]; i; i = es[i].nxt){
int v = es[i].v;
if(dis[v] > dis[s] + es[i].w) {
dis[v] = dis[s] + es[i].w;
myq.push(node(v, dis[v]));
inq[v] = 1;
}
}
}
}
int main(){
int a, b, c;
scanf("%d %d", &n, &m);
for(int i = 1; i <= m; i++){
scanf("%d %d %d", &a, &b, &c);
adde(a - 1, b, b - (a - 1) - c);
}
for(int i = 1; i <= n; i++){
adde(i, i - 1, 0);
}
for(int i = 1; i <= n; i++) adde(i - 1, i, 1);
memset(dis, 0x3f, sizeof dis);
dijkstra(0);
for(int i = 1; i <= n; i++){
if(dis[i] - dis[i - 1] == 1) printf("0 ");
else printf("1 ");
}
return 0;
}