猫史档案馆

 

 

 

 

1.差分约束系统（system of difference constraints）

 

 

 · 差分约束是求解n元一次特殊不等式组的一种方法。

 · 差分约束系统包含n个变量和m个约束条件，每个约束条件都是一个关于两个变量的一次不等式，每个不等式形如X[i]-X[j]<=A[k]，其中1<=i,j<=n，1<=k<=m，X[i]、X[j]为变量，A[k]为常数。

 · 引理：若{Xi}为差分约束系统的一组解，v为常数，那么{Xi喵}也是一组解。这个不等式组要么无解，要么有无数组解。

 · 差分约束可以转化为图论中的单源最短路问题求解。

 

总的来说，含有m个形如

x_i−x_j≤k

的形式的约束条件的n元不等式组成为差分约束系统（system of difference constraints.）

 

 

2.具体求法

 

 

概说

 

 · 差分约束系统中的每个不等式都与最短路中的三角形不等式 dist[v]<=dist[u]+edge(u,v) 形似。可以把差分约束系统转化成一张图。

 · 把变量Xi看做有向图中的点i，对不等式X[i]-X[j]<=A[k]从j向i连一条有向边，边权为A[k]。建立一个源点，向每个点连一条有向边，边权为0。从源点出发求单源最短路，X[i]=dist[i]就是一组可行解。有负环说明无解。

 · 若对X[i]有范围限制，可用X[i]与源点之间的约束表示。

 · 不等式>=号时用最长路解决，此时有正环说明无解。

 

 

建图

 

 

比如

X[1]-X[5] <= 1

可以得出

X[1]<= X[5] + 1

同时源点到点i的距离小于等于源点到点j的距离加上点j到点i的距离，

即

Dis(i) <= Dis[j] + edge(j, i)

因此对于每一对

X[i]-X[j]<=A[k],

就从j到i连一条权是A[k]的边即可。

 

那么为什么有负环就无解？

从跑图的角度来看，就会一直跑下去。我们再来看看恢复到原来的不等式里。

比如：

看左图。

由这个图，可以列出：

X[1]-X[2]<0

X[2]-X[3]<0

X[3]-X[1]<0

很容易得出，X[1]<X[2],X[2]<X[3],即X[1]<X[3]

那么从第三个式子又能看出什么呢？X[1]>X[3].

所以不等式无解.

 

 

 

 

 

 

 

 

3.例题讲解

 

 

[Usaco2005 dec]Layout 排队布局

 

题目描述

当排队等候喂食时，奶牛喜欢和它们的朋友站得靠近些。FJ有N头奶牛，编号从1到N，沿一条直线站着等候喂食。奶
牛排在队伍中的顺序和它们的编号是相同的。因为奶牛相当苗条，所以可能有两头或者更多奶牛站在同一位置上。即
使说，如果我们想象奶牛是站在一条数轴上的话，允许有两头或更多奶牛拥有相同的横坐标。一些奶牛相互间存有好
感，它们希望两者之间的距离不超过一个给定的数L。另一方面，一些奶牛相互间非常反感，它们希望两者间的距离
不小于一个给定的数D。给出ML条关于两头奶牛间有好感的描述，再给出MD条关于两头奶牛间存有反感的描述。你
的工作是：如果不存在满足要求的方案，输出-1；如果1号奶牛和N号奶牛间的距离可以任意大，输出-2；否则，计算
出在满足所有要求的情况下，1号奶牛和N号奶牛间可能的最大距离。

 

输入描述

第1行:三个空格分隔的整数:N、ML和MD。ML+1:每行包含3个以空格分隔的正整数:A、B、D，其中1 <= A < B <=
n。* ML + 2行. .ML+MD+1:每行包含三个以空格分隔的正整数:A、B、D，其中1 <= A < B <= N.奶牛A和奶喵之间
的距离必须至少为D。

 

输出描述

第1行:单个整数。如果不可能排列，输出-1。如果母牛1和牛N可以任意地相隔很远，输出-2。否则，输出奶牛1和N
之间的最大可能距离。

 

输入样例

4 2 1
1 3 10
2 4 20
2 3 3

 

输出样例

27

 

数据规模

2<=N<=1000

1<=ML,MD<=10000，1<=L,D<=1000000

 

一道裸的差分约束系统

#include<bits/stdc++.h>
using namespace std;
int n,ml,喵,a,b,c,fst[10100],nex[50010],v[50010],w[50010],cnt,vis[10100],dis[10100],tim[10100];
queue<int> q;
void add(int a,int b,int c){
    nex[++cnt]=fst[a];fst[a]=cnt;v[cnt]=b;w[cnt]=c;
    return ;
}
int spfa(int k){
    memset(dis,0x7f/3,sizeof(dis));
    memset(vis,0,sizeof(vis));
    memset(tim,0,sizeof(tim));
    q.push(k);dis[k]=0;vis[k]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();tim[u]++;
        vis[u]=0;
        if(tim[u]>n)return -1;
        for(int i=fst[u];i!=-1;i=nex[i]){
            if(dis[v[i]]>dis[u]+w[i]){
                dis[v[i]]=dis[u]+w[i];
                if(!vis[v[i]]){
                    q.push(v[i]);
                    vis[v[i]]=1;
                }
            }
        }
    }
    if(dis[n]>1e8)
    return -2;
    return dis[n];
}
int main(){
    memset(fst,-1,sizeof(fst));
    cin>>n>>ml>>喵;
    for(int i=1;i<=ml;i++){
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    for(int i=1;i<=喵;i++){
        scanf("%d%d%d",&a,&b,&c);
        add(b,a,-c);
    }
    for(int i=1;i<n;i++)add(i+1,i,0);
    for(int i=1;i<=n;i++)add(0,i,0);
    int sp=spfa(0); 
    if(sp<=-1){
        cout<<sp;
        return 0;
    }
    else cout<<spfa(1);
    return 0;
}

 

 

4.模板代码

最后附上模板代码

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 10;

int n, m, cnt, Number[N]/*统计每一个点存入的次数*/, dist[N] /*距离*/, head[N];
bool visit[N];

struct Node {
    int u, v, nxt;
} a[N];

inline void init () {
    memset (head, -1, sizeof (head));
    memset (dist, -1, sizeof (dist)); // 这里一定要初始化！否则会凉凉
    Number[0] = 1; // 存源点 x0 次数为 1
    dist[0] = 0; // 源点距离为 0
    visit[0] = true; // 标记源点 x0 已在队列中
}

inline void add (int u, int v, int w) { // 加边板子不解释？
    a[++ cnt].u = v;
    a[cnt].v = w;
    a[cnt].nxt = head[u];
    head[u] = cnt;
}

inline bool SPFA () { // SPFA 板子，稍改动
    queue <int> q;
    q.push (0); // 存入最初的源点 x0
    while (!q.empty ()) {
        int u = q.front (); q.pop (); // 出队
        visit[u] = false;
        for (register int i = head[u]; ~i; i = a[i].nxt) { // 遍历与 u 联通的所有点
            int v = a[i].u;
            if (dist[v] < dist[u] + a[i].v) { // 进行松弛操作
                dist[v] = dist[u] + a[i].v;
                //由于更新了节点，所以后续以这个为基础的最短路也要更新，所以如果已经在队列里面了就不用加入，不在的话就加入更新后续节点
                if (!visit[v]) {
                    q.push (v);
                    visit[v] = true; // 标记这个点在队列中了
                    ++ Number[v]; // 存入点 v 的次数加一
                    if (Number[v] > n) return false; // 如果这个点加入超过了 n 次就说明存在负环，直接无解返回 false
                }
            }
        }
    }
    return true;
}

inline int read () { // 快读就不解释了
    int Res = 0, f = 1; char ch = getchar ();
    while (!isdigit (ch) && ch ^ '-') ch = getchar ();
    if (ch == '-') {f = -1; ch = getchar ();}
    while (isdigit (ch)) {Res = (Res << 1) + (Res << 3) + (ch ^ '0'); ch = getchar ();}
    return Res * f;
}

inline void input () { // 输入
    n = read ();
    m = read ();
    for (register int i = 1; i <= m; ++ i) {
        int u=read();
        int v=read();
        int w=read();
        add (u, v, -w); // 存负边以负的形式求最长路
    }
    for (register int i = 1; i <= n; ++ i) add (0, i, 0); // 把源点 x0 与所有点连接
}

int main () {
    init ();
    input ();
    if (SPFA()){ //有解
        for(register int i=1;i<=n;++i)printf("%d ",dist[i]);
    } else printf ("NO\n"); //无解
    return 0;
}