属于简单知识点的补档。
差分约束
差分约束系统 是一种特殊的 \(n\) 元一次不等式组，包含 \(n\) 个变量 \(x_1,\dots,x_n\) 和 \(m\) 个约束条件，每个约束条件形如 \(x_i-x_j\le c_k\)，其中 \(c_k\) 是常数。我们要解决的问题是求出 \(x_1,\dots,x_n\) 的一组解。
差分约束问题是最短路算法的一种巧妙应用。我们发现，差分约束系统中的每个约束条件 \(x_i-x_j\le c_k\) 都可以变形成 \(x_i\le x_j+c_k\)，这不由得让我们想到单源最短路中的三角形不等式 \(\text{dis}(v)\le\text{dis}(u)+w\)。因此，我们把每个未知数 \(x_i\) 看作图中的一个节点，对每一个约束条件 \(x_i-x_j\le c_k\) 连边。
连边方法有两种：
- 连一条 \(x_j\to x_i\) 的边权为 \(c_k\) 的边之后跑最短路，最终求出来的解是 \(x_i\le0\) 时所有 \(x\) 的最大值；
- 连一条 \(x_i\to x_j\) 的边权为 \(-c_k\) 的边之后跑最长路，最终求出来的解是 \(x_i\ge0\) 时所有 \(x\) 的最小值。
这两种方法不能混用。
注意这样连完边之后图不一定联通，此时我们只需定义一个 “超级源点” \(0\)，并对所有 \(i\) 连 \((0,i,0)\) 的边。然后，跑最短/最长路。
至于题目中要求判断无解，我们只需用 SPFA 判断是否存在负环即可。若存在负环，则无解；否则，\(x_i=\text{dis}(i)\) 就是题目要求的一组解。
例 1 P5960 【模板】差分约束
constexpr int MAXN=5005;
int n,m,head[MAXN],tot;
struct{
int v,to,w;
}e[MAXN<<1];
void addedge(int u,int v,int w){
e[++tot]={v,head[u],w};
head[u]=tot;
}
int dis[MAXN],cnt[MAXN];
bool vis[MAXN];
queue<int>q;
void spfa(){
memset(dis,0x3f,sizeof(int)*(n+5));
dis[0]=0;
vis[0]=1;
q.emplace(0);
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i;i=e[i].to)
if(dis[e[i].v]>dis[u]+e[i].w){
dis[e[i].v]=dis[u]+e[i].w;
if(!vis[e[i].v]){
vis[e[i].v]=1;
q.emplace(e[i].v);
if(++cnt[e[i].v]>n){
puts("NO");
exit(0);
}
}
}
}
}
int main(){
n=read(),m=read();
for(int i=1,u,v,w;i<=m;++i){
u=read(),v=read(),w=read();
addedge(v,u,w);
}
for(int i=1;i<=n;++i) addedge(0,i,0);
spfa();
for(int i=1;i<=n;++i) write(dis[i],' ');
return putchar('\n'),fw,0;
}
例 2 P1993 小 K 的农场
把所有不等式转化为标准形式即可。注意连边方法一定一定不能弄混。
#include<bits/stdc++.h>
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
using namespace std;
char buf[1<<20],*p1=buf,*p2=buf;
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
constexpr int MAXN=5005;
int n,m,head[MAXN],tot;
struct{
int v,to,w;
}e[MAXN<<1];
void addedge(int u,int v,int w){
e[++tot]={v,head[u],w};
head[u]=tot;
}
int dis[MAXN],cnt[MAXN];
bool vis[MAXN];
queue<int>q;
void spfa(){
memset(dis,0x3f,sizeof(int)*(n+5));
dis[0]=0;
vis[0]=1;
q.emplace(0);
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i;i=e[i].to)
if(dis[e[i].v]>dis[u]+e[i].w){
dis[e[i].v]=dis[u]+e[i].w;
if(!vis[e[i].v]){
vis[e[i].v]=1;
q.emplace(e[i].v);
if(++cnt[e[i].v]>=n){
puts("No");
exit(0);
}
}
}
}
}
int main(){
n=read(),m=read();
for(int i=1,op,u,v;i<=m;++i){
op=read(),u=read(),v=read();
switch(op){
case 1: addedge(u,v,-read());break;
case 2: addedge(v,u,read());break;
case 3: addedge(u,v,0),addedge(v,u,0);break;
}
}
for(int i=1;i<=n;++i) addedge(0,i,0);
spfa();
return puts("Yes"),0;
}
01BFS
01BFS 用于解决边权只有 \(0\) 和 \(1\) 的最短路问题，复杂度是 \(O(n+m)\) 的，可以避免一般最短路算法的 \(\log\)。
方法：用一个双端队列 deque，把边权为 \(0\) 的边放到队首，边权为 \(1\) 的边放到队尾。
例 [AGC056C] 01 Balanced
这道题的主要部分在这篇题解里。这里只放它的 01BFS 部分。
void bfs(){
memset(dis,-1,sizeof(int)*(n+5));
dis[0]=0;
deque<int>q;
q.emplace_back(0);
while(!q.empty()){
int u=q.front();
q.pop_front();
for(int i=head[u];i;i=e[i].to){
if(~dis[e[i].v]) continue;
dis[e[i].v]=dis[u]+e[i].w;
e[i].w?q.emplace_back(e[i].v):q.emplace_front(e[i].v);
}
}
}