差分约束
背景
考虑一个有\(n\)个不等式的不等式组
\[
\cases{x_1 - x_1' \leqslant y_1 \\x_2 - x_2' \leqslant y_2 \\\vdots \\x_n - x_n' \leqslant y_n \\}
\]
问该不等式组是否有整数解,如果有给出一组整数解
思想
主体
考虑在有向图\(G\)中,如果存在从\(u\)出发到\(v\)的边\((u,v)\),那么\(dis[v] \leqslant dis[u] + weight\ of\ (u,v)\),其中\(dis[i]\)表示为从源点\(s\)(一般取0,不理解的话别着急,下面细节部分具体讲,也可以看板子理解一下)到点\(i\)的最短距离。那么我们可以把上面的不等式组转化为一张有向图\(G\),不难看出以源点\(s\)为起始点,跑一遍后最短路,最后得到的\(dis[]\)数组是一组解。那什么情况会没有整数解呢?我们考虑由不等式转化得到的有向图\(G\),如果有向图\(G\)压根没有环,那肯定是有解的;如果有向图\(G\)有环,且所有环为非负环,那也有整数解解;如果有向图\(G\)存在负环,那必然无解,因为存在负环时\(dis\)可以跑到\(-\infty\)。简单画了个图直观理解一下\(\downarrow\)
细节
主要思想就是建图跑spfa(不知道spfa可以去百度一下)找负环,如果没负环就输出\(dis[]\)数组;如果有负环就无解。说是这么说,代码的具体实现实际上还有讲究:
- 关于源点:为啥整这个玩意儿?我们建的图是有向图,并不是所有点都能当起点的,况且建起来的图很可能是不连通的,为了减少麻烦,使得一遍spfa就能跑完所有的点,我们加入一个源点(有些博主称它为超级源点),并在源点和所有其它点之间加一条权重为0,有源点出发指向其它点的有向边。因为很多题的点编号范围是\([1,n]\),所有源点一般取0
- 关于如何找负环:因为一个点,最多被除自己以外的所有点松弛一次,所以如果一个点被松弛的次数\(\geqslant n\),就说明有负环
板子
说是板子,其实就是洛谷p5960的板子题
#include <cstdio>
#include <queue>
#include <vector>
const int N = 5e3 + 5;
const int INF = 0x7fffffff;
int n, m, s;
int dis[N], num[N];
bool exist[N];
struct Edge {
int v, w;
Edge() {}
Edge(int _v, int _w) : v(_v), w(_w) {}
};
std::vector<Edge > g[N];
inline void init() {
s = 0; // 源点
for(int i = 0; i <= n; i++) {
g[i].clear();
dis[i] = INF;
exist[i] = false;
}
dis[s] = 0;
for(int i = 1; i <= n; i++)
g[s].push_back(Edge(i, 0));
}
std::queue<int >q;
bool spfa() {
while(!q.empty()) q.pop();
q.push(s); exist[s] = true;
while(!q.empty()) {
int u = q.front(); q.pop(); exist[u] = false;
for(int i = 0; i < g[u].size(); i++) {
int v = g[u][i].v;
if(dis[v] > dis[u] + g[u][i].w) {
dis[v] = dis[u] + g[u][i].w;
if(++num[v] >= n)
return true;
if(!exist[v]) {
q.push(v);
exist[v] = true;
}
}
}
}
return false;
}
int main() {
scanf("%d%d", &n, &m);
init();
for(int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
g[v].push_back(Edge(u, w));
}
if(spfa()) puts("NO"); // 无解
else
for(int i = 1; i <= n; i++)
printf("%d ", dis[i]);
return 0;
}
不是\(\geq\)的情况
如果约束是\(x_i-x_i' \geq y_i\)的形式,有两种解决办法:
- 不等式两边取负
- 把它看作是最长路建图,跑最长路即可
例题
洛谷 P5960 板子题
洛谷 P3275(SCOI2011)糖果
题解有点长,大家可以直接看洛谷上的题解,第一篇讲得很好传送门