没什么好写的。

算法思路

有 \(n\) 个未知数 \(x_i\)，给定 \(m\) 个形如 \(x_i-x_j\le c\)(\(c\) 为常数)的不等式。

\(\begin{cases} x_{a_1}-x_{b_1}\le c_1 \\ x_{a_2}-x_{b_2}\le c_2 \\ \dots\\ x_{a_3}-x_{b_3}\le c_3\\ \end{cases}\)

求一组最大解和最小解。使得所有的不等式成立。

我们以最小解为例讲解。

观察不等式，发现 \(x_i-x_j\le c\) 可以转换成类似 SPFA 中的三角形不等式的形式，即 \(x_i\le x_j+c\)。我们把 \(x_i\) 抽象成点 \(i\) 距离起点的最短路，不等式中的 \(c\) 就是边权。跑一趟单元最短路就可以了。但是不保证所有的点联通。所以规定一个源点 \(x_0=0\) 为起点，将其与每个 \(x_i\) 连一条边权为 \(0\) 的有向边。

差分约束中存在无解的情况，也就是说在任意一刻我们都无法求得正解，也就是说差分约束系统形成的图中存在负环，直接用 SPFA 判断即可

因为 \(x_i\le x_j+c\) 是对 \(x_i\) 取值上限的限制。我们也可以将原不等式变形为 \(x_j+c\ge x_i\)。这样是对其取值下限的约束，跑最长路即可，无解情况是存在正环。方法一求的是最大解，方法二求的是最小解。判负环的方式类似。

例题

例 \(1\)：【模板】差分约束

没说最大解或最小解，直接求一个就好

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int N=5e3+10;
int idx,ver[N],to[2*N],nxt[2*N],val[2*N],n,m,mk[N],dis[N],d[N];
queue<int>q;
void add(int x,int y,int z){
    to[++idx]=y,nxt[idx]=ver[x],ver[x]=idx,val[idx]=z;
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1,u,v,w;i<=m;i++){
        scanf("%d %d %d",&u,&v,&w);
        add(v,u,w);mk[u]=1;
    }
    for(int i=1;i<=n;i++)if(!mk[i])add(0,i,0);
    memset(dis,0x3f,sizeof(dis));
    memset(mk,0,sizeof(mk));
    q.push(0),mk[0]=1,dis[0]=0,d[0]=1;
    while(q.size()){
        int t=q.front();q.pop();
        mk[t]=0;
        for(int i=ver[t];i;i=nxt[i]){
            int tp=to[i];
            if(dis[t]+val[i]<dis[tp]){
                dis[tp]=dis[t]+val[i];
                if(!mk[tp]){
                    if(++d[tp]>=n){
                        cout<<"NO"<<endl;
                        return 0;
                    }
                    q.push(tp),mk[tp]=1;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout<<dis[i]<<" ";
    }
    return 0;
}

例 \(2\)：小 K 的农场

主要将转换边权，设第 \(i\) 个农场有 \(x_i\) 个单位的作物。

• 情况一：\(x_a-x_b\ge c\) 可转换为 \(x_b\le x_a-c\)
• 情况二：\(x_a-x_b\le c\) 可转换为 \(x_a\le x_b+c\)
• 情况二：\(x_a=x_b\) 可转换为 \(x_a\le x_b+0,x_b\le x_a+0\)

直接跑最短路即可

例 \(3\)：[SCOI2011] 糖果

数据非常大，直接跑 SPFA 行不通。

转换为边权后，发现边权只有 \(0,1\) 两种。我们可以考虑缩点，先求出原图中的强连通分量。如果强连通分量中的两个点之间有 \(1\) 边权。则肯定无解，因为强连通分量中的所有点点权应当一样。

缩点后跑拓扑排序就好

例 \(4\)：[1007] 倍杀测量者

显然，\(t\) 越大，女装的人越少，\(t\) 越小，女装的人越多。答案具有单调性，直接二分答案。判定很简单，我们先求出所有人不女装的不等式，如果题目中给定的所有不等式满足，则没人会女装。反之则一定有人女装。找到最大的不满足不等式的 \(t\) 就好。

我们发现，对于类似 \(x_a\ge (k-t)\times x_b\) 直接求会有精度误差。所以还是转换成三角形不等式。\(\log_2(x_a)\ge\log2(x_b)+\log2(k-t)\)，就能解决问题。

另外，对于差分约束中的有常量的情况，例如：已知 \(k\) 的的点权 \(c_k\)。我们的维护办法是，连两条边，分别是 \((k,0,c_k),(k,0,-c_k)\)。这样就成功表示出了常量。

真的无法忍受有精度问题和带有高中数学知识的题目！

毕竟我连小学数学都玩不明白。

The End

感觉没什么用，大概会一点就好了，以后慢慢练。

我怎么连不等式都转换不好

upd：差分约束简单？什么人机话，我当时到底有多糖啊！

马上补一下差分约束