简述
差分约束系统，是由 \(n\) 个元素和 \(m\) 个约束条件构成的，其中每个约束条件形如 \(x_i-x_j\le y_k\)。
求解
移项得到 \(x_i\le x_j+y_k\)，这样三角形不等式的形式类似最短路中的松弛，即由 \(j\) 向 \(i\) 连 \(y_k\) 权值的边，最短路即满足约束条件。
这样便需要一个源点，原图不一定联通，因此建出超级源点 \(n+1\)，且规定 \(x_i\le 0\)，即 \(x_i \le x_{n+1}+0\)，由 \(n+1\) 向 \(i\) 连 \(0\) 权值的边。
这样的负权图最短路可以使用 已死算法 SPFA 来求出。
点击查看代码
int n,m;
struct Graph{
struct edge{
int v,w;
edge()=default;
edge(int v_,int w_):v(v_),w(w_){}
};
vector<edge> E[maxn];
inline void add_edge(int u,int v,int w){
E[u].push_back(edge(v,w));
}
int dis[maxn],cnt[maxn];
bool vis[maxn];
inline void SPFA(){
queue<int> q;
memset(dis,0x3f,sizeof(dis));
dis[n+1]=0,cnt[n+1]=0,vis[n+1]=1;
q.push(n+1);
while(!q.empty()){
int u=q.front();
vis[u]=0;
q.pop();
for(edge e:E[u]){
int v=e.v,w=e.w;
if(dis[u]+w<=dis[v]){
dis[v]=dis[u]+w,cnt[v]=cnt[u]+1;
if(cnt[u]>n) return printf("NO\n"),void();
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
}
for(int i=1;i<=n;++i) printf("%d ",dis[i]);
printf("\n");
}
}G;
int main(){
n=read(),m=read();
for(int i=1;i<=n;++i) G.add_edge(n+1,i,0);
for(int i=1;i<=m;++i){
int u=read(),v=read(),w=read();
G.add_edge(v,u,w);
}
G.SPFA();
return 0;
}
对约束条件的调整
一些简单的变形：
-
\(x_i-x_j\le k\Rightarrow w(j,i)=k\)
-
\(x_i-x_j\ge k\Rightarrow x_j-x_i\le -k\Rightarrow w(i,j)=-k\)
-
\(x_i=x_j\Rightarrow x_i-x_j\le 0\land x_j-x_i\le 0\Rightarrow w(i,j)=w(j,i)=0\)
-
\(x_i-x_j< k\Rightarrow x_i-x_j\le k-1\Rightarrow w(j,i)=k-1\)
-
\(x_i-x_j> k\Rightarrow x_i-x_j\ge k+1\Rightarrow w(i,j)=-k-1\)
对解的特殊限制
事实上，当 \((x_1,x_2,\cdots,x_n)\) 为一组解时，\((x_1+k,x_2+k,\cdots,x_n+k)\) 同样为一组解。因此不等式组要么无解要么有无数组解，无解情况即为没有最短路也就是存在负环。
而在初始的设计中，\(x_i\le 0\)，当需要求出特定范围的解时，可以通过限定 \(dis_{n+1}\) 的初始值或 \(w(n+1,i)\) 的值来规定。假设将值修改为 \(c\)，则本质上是有 \(x_i\le c\) 的限定。
值得注意的是，最短路求出的结果一定是所有解中最大的。证明考虑最短路树，树边一定满足 \(x_i=x_j+w(j,i)\) 而一旦增加 \(x_j\) 的值就会使答案不合法。
如果要求出满足 \(x_i\ge k\) 的所有解中和最小的值，该如何处理？
首先可以通过变号得到 \(-x_i\le -1\)，这一点可以对 \(dis_{n+1}\) 进行修改。这样所有的 \(x\) 值都已经取反，则 \(x_i=x_j+w(j,i)\) 变作 \(-x_j=-x_i+w(j,i)\)，即 有向边方向改变，边权不变，此时最短路得到的最大解与要求最小解互为相反数。
例题
洛谷-P3275 [SCOI2011] 糖果
建模比较容易，关键是 SPFA 被卡了。
发现边权只有 \(0\) 或 \(-1\)，那么一个 SCC 中存在边权 \(-1\) 即无解，这样每个 SCC 都一定相等，最短路用拓扑排序求出。
点击查看代码
int n,m;
ll ans;
struct Grpah{
struct edge{
int v,w;
edge()=default;
edge(int v_,int w_):v(v_),w(w_){}
};
vector<edge> E[maxn];
inline void add_edge(int u,int v,int w){
E[u].push_back(edge(v,w));
}
int dfn[maxn],low[maxn],dfncnt;
int st[maxn],top;
int scc[maxn],scccnt,siz[maxn];
inline void Tarjan(int u){
dfn[u]=++dfncnt,low[u]=dfn[u];
st[++top]=u;
for(edge e:E[u]){
int v=e.v;
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!scc[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
++scccnt;
while(st[top]!=u){
scc[st[top]]=scccnt;
++siz[scccnt];
--top;
}
scc[u]=scccnt;
++siz[scccnt];
--top;
}
}
vector<edge> dagE[maxn];
int deg[maxn];
int dis[maxn];
inline void solve(){
for(int i=1;i<=n;++i){
if(!dfn[i]) Tarjan(i);
}
for(int u=1;u<=n;++u){
for(edge e:E[u]){
int v=e.v;
if(scc[u]==scc[v]){
if(e.w==-1) return printf("-1\n"),void();
}
else{
dagE[scc[u]].push_back(edge(scc[v],e.w));
++deg[scc[v]];
}
}
}
for(int i=1;i<=scccnt;++i){
dagE[scccnt+1].push_back(edge(i,-1));
++deg[i];
}
queue<int> q;
memset(dis,0x3f,sizeof(dis));
dis[scccnt+1]=0;
q.push(scccnt+1);
while(!q.empty()){
int u=q.front();
q.pop();
for(edge e:dagE[u]){
int v=e.v,w=e.w;
if(dis[u]+w<dis[v]) dis[v]=dis[u]+w;
--deg[v];
if(!deg[v]) q.push(v);
}
}
for(int i=1;i<=scccnt;++i){
ans-=1ll*siz[i]*dis[i];
}
printf("%lld\n",ans);
}
}G;
int main(){
n=read(),m=read();
for(int i=1;i<=n;++i) G.add_edge(n+1,i,-1);
for(int i=1;i<=m;++i){
int opt=read(),u=read(),v=read();
if(opt==1) G.add_edge(u,v,0),G.add_edge(v,u,0);
else if(opt==2) G.add_edge(u,v,-1);
else if(opt==3) G.add_edge(v,u,0);
else if(opt==4) G.add_edge(v,u,-1);
else G.add_edge(u,v,0);
}
G.solve();
return 0;
}
参考资料
-
OI Wiki