差分约束系统

0. 前言

你需要知道：

1. SPFA
2. 图论基础建模
3. 不等式基础

1. 负环

为什么先讲负环啦？是因为差分约束是要用负环的。

给定一张有向图（无向图看作两条等权边），每条边有权值。若一个边权值是负数，那么我们称这个边为负权边。

若图中存在一个环，如果环上的边有负权边，那么我们称这个为负环。

例如4,5,7构成负环，而5,8,1构成正环

我们可以用最短路算法来跑判断负环，什么你跟我说拓扑排序？如果一张图既有正环也有负环那判断不出来啊，拓扑只能判环不能判是哪个类型的。

但是不是所有都能用…

算法	适用条件	时间复杂度
Dijkstra	不可以，负边权会对之后结果造成影响不一定最小。	$O(n^2)\rightarrow O(m \log n)$
Bellman-Ford	可以，无负环的时候最短路边数一定小于$n$ ，无负环的情况下走$n-1$ 次后一定收敛。	$O(nm$)
SPFA	同Bellman-Ford	$O(nm)\rightarrow O(km)$

所以也就只能用SPFA了…

所以怎么判断？很简单，只需要开个桶，如果一个点走了不少于$n$ 次那么一定有负环。那么就可以了。

bool spfa(){ //1有负环 0无负环
    queue<int> q;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(auto e:adj[u]){
            if(dis[e.v]<dis[u]+e.w){
                dis[e.v]=dis[u]+e.w;
                if(!vis[e.v]){
                    vis[e.v]=1;
                    q.push(e.v);
                    cnt[e.v]++;
                    if(cnt[e.v]>=n) return 1; // 不少于n次一定有
                }
            }
        }
    }
    return 0;
}

你跟我说负边权图被卡SPFA了？可以考虑一下DAG跑。

2.差分约束系统

差分约束系统是一种特殊的$N$ 元一次不等式组，有$N$ 个变量与$M$ 个约束条件（其实就是不等式）。

所以为什么叫差分约束呢？是因为每一个不等式都是两个变量作差得到的：

$$\begin{cases} X_2-X_{1} \le C_{1} \\ X_3-X_{2}\le C_{2} \\ X_4-X_{3}\le C_{3} \\ \end{cases}$$

如上，都是作差得到的，所以叫差分约束了。

我们取第一个出来，我们变变形：

$$X_2 \le X_{1}+C_{1}$$

是不是有点像dis[e.v]<dis[u]+e.w，及其相似。

我们怎么求解这些方程组呢？我们可以像上面的式子一样，我们就让后面的连前面的，例如下面的式子：

$$X_i-X_{j}\le C_i$$

我们从$X_j\rightarrow X_i$ 连边，边权为$C_i$。这样就可以了，但是这个有多组解（两边统一加上一个常数$d$ 不等式仍然成立），而且还有负数解，我们不喜欢负数解，但是我们可以加一个源点$X_0$，我们不妨令$X_0=0$ ，让后显然有$X_i-X_{0}\le 0$ ，那么$0\rightarrow i$ 连边权为$0$ 的边，这样就可以保证都是整数解了。

不妨设$dis[0]=0$ ，让后以此为起点跑单源最短路，这样我们就能求出一组解了。如果有负环那么说明不等式不成立，那么就无解。

2.1 大于等于推导

当然做题你会发现如下的式子：

$$X_i-X_{j}\ge C_i$$

这个时候有两个方法，第一个两边都取负，不等式变号，就有$X_j-X_{i}\le -C_i$，九二可以连边了；第二种方法就是改成跑单源最长路，如果有正环说明无解。

2.2 等于式推导

还有如下的式子：

$$X_i=X_j$$

其实可以转化成：

$$X_i=X_{j}\Rightarrow \begin{cases} X_i-X_{j}\le 0 \\ X_j-X_{i}\le 0 \end{cases}$$

2.3 分式推导

更有甚者：

$$\frac{X_i}{X_{j}}\le C_i$$

这是差分约束吗？其实也可以变变形，回忆对数相减代表这什么，其实就可以转化为：

$$\log\frac{X_i}{X_{j}}=\log_aX_i-\log_aX_{j}\le \log_{a}C_i$$

做就可以了，这个$a$ 取大于0的实数即可，但是取2就可以了。

总结一下：

差分约束	转化后	连边(w为边权)
$X_i-X_j\ge c_i$	$X_j-X_{i}\le -C_i$	$i \rightarrow j,w_i=-C_i$
$X_i-X_{j}\le C_i$	同前	$j \rightarrow i,w_i=C_i$
$X_i=X_j$	$X_i-X_{j}\le 0,X_j-X_{i}\le 0$	$i \leftrightarrow j,w_i=0$
$\frac{X_i}{X_{j}}\le C_i$	$log_aX_i-\log_aX_{j}\le \log_{a}C_i$	$j\rightarrow i,w_i=\log_a C_i$

让后跑spfa就可以了www。

2.1 例题——Interval

例题：六倍经验——SP116 Interval

有$n$ 个区间，在区间$[a_i,b_i]$ 中至少取任意互不相同的$c_i$ 个整数。求在满足$n$ 个区间的情况下，至少要取多少个正整数。

做法1：差分约束

其实就是让我们选数，变量就是数的数量。

不难发现有$x[b_i]-x[a_{i-1}]\ge c_i$，但是为了保证我们的解有意义，我们还需要添加$$1\ge s[i]-s[i-1] \ge 0$，保证不能选负数个数，又不能多选出来。

但是$0\le a_{i}\le 5\times 10^4$，所以我们要从$-1$开始，很难受，其实也很简单，只需要都加上一即可让后从0开始即可了。

故代码如下：

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=5e4+15,INF=1e9;
struct Edge{
    int v,w;
};
int n,T,dis[MN];
vector<Edge> adj[MN];
bool vis[MN];

void init(){
    for(int i=1;i<=n;i++){
        adj[i].clear();
        dis[i]=-INF;
        vis[i]=0;
    }
}

void spfa(){
    queue<int> q;
    q.push(0);
    vis[0]=1;
    dis[0]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(auto e:adj[u]){
            if(dis[e.v]<dis[u]+e.w){
                dis[e.v]=dis[u]+e.w;
                if(!vis[e.v]){
                    q.push(e.v);
                    vis[e.v]=1;
                }
            }
        }
    }
}

void solve(){
    int maxp=-1;
    cin>>n;
    init();
    for(int i=1;i<=n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        adj[a].push_back({b+1,c});
        maxp=max(maxp,b+1);
    }
    for(int i=1;i<=maxp;i++){
        adj[i-1].push_back({i,0});
        adj[i].push_back({i-1,-1});
    }
    spfa();
    cout<<dis[maxp]<<'\n';
}

int main(){
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

2.2 强联通分量优化——洛谷P10935，3275

我们用一个正整数来表示恒星的亮度，数值越大则恒星就越亮，恒星的亮度最暗是$1$。
现在对于$N$ 颗我们关注的恒星，有$M$ 对亮度之间的相对关系已经判明。
你的任务就是求出这$N$ 颗恒星的亮度值总和至少有多大。
输入格式：
第一行给出两个整数$N$ 和$M$。

之后$M$ 行，每行三个整数$T, A, B$，表示一对恒星$(A, B)$ 之间的亮度关系。恒星的编号从$1$ 开始。
如果$T = 1$，说明$A$ 和$B$ 亮度相等。
如果$T = 2$，说明$A$ 的亮度小于$B$ 的亮度。
如果$T = 3$，说明$A$ 的亮度不小于$B$ 的亮度。
如果$T = 4$，说明$A$ 的亮度大于$B$ 的亮度。
如果$T = 5$，说明$A$ 的亮度不大于$B$ 的亮度。
无解输出$-1$
$1\le N \le 10^5,1\le M \le 10^6$

首先我们归类一下能直接看出来的式子，这里我们先都转成大于式子，不知道大于式子怎么差分约束的看2.1：

$$\begin{cases} X_A-X_B\ge0,X_B-X_{A} \ge 0 & A=B \\ ? & A<B \\ X_A-X_{B} \ge 0 & A\ge B \\ ? & A>B \\ X_B-X_{A}\ge 0 & A\le B \end{cases}$$

我们解决一下小于和大于的情况：

$$\begin{aligned} X_A-X_{B}& < 0 \\ X_B-X_{A}& > 0 \\ \because X_B,X_{A} & \in \mathbb{Z} \\ \therefore X_B-X_{A} & \in \mathbb{Z} \\ \therefore X_B-X_{A}& \ge 1 \end{aligned}$$

大于情况同理。

整理一下：

$$\begin{cases} X_A-X_B\ge0,X_B-X_{A} \ge 0 & A=B \\ X_B-X_{A}\ge 1 & A<B \\ X_A-X_{B} \ge 0 & A\ge B \\ X_A-X_{B}\ge 1 & A>B \\ X_B-X_{A}\ge 0 & A\le B \end{cases}$$

让后我们就可以用SPFA跑，于是代码如下…？怎么$N \le 10^5$。

$O(NM)$炸掉了呜呜呜。怎么做？

观察原图，不难发现每个边的边权不是1就是0，我们判断无解怎么判断？那当然是找环，不难发现如果有环并且环上一旦有权为1的边就是无解（正环无解）。

但是怎么求有向图的环呢？而且复杂度还不能$O(NM)$…Tarjan大法好！强联通分量复杂度$O(N+M)$。

但是不对啊，还有有解的情况呢？怎么求，其实也好，如果有解那么一个强联通分量的答案一定是相同的（因为要求最小所以都填一样就行了），那么直接缩点，缩点完后就是一个DAG，跑拓扑排序单源最长路就可以了。

什么？你不会DAG的单源最长路？

$$dis[v]=\max\limits_{v\in son(u)}(dis[v],dis[u]+w_{edge})$$

这是递推公式，因为初始$X$ 最小为1，所以初始化入度为0的节点$dis[u]=0$ ，答案怎么算？也很简单。

$$ans=\sum\limits_{i=1}^{dcc}cnt_{i} \times dis_i$$

其中$dcc$ 是强联通分量的个数，$cnt$ 是强联通分量节点个数。

所以代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=1e6+15;
struct Edge
{
    int v,w;
};
int n,m,tot,dcc,top,s[MN],color[MN],in[MN],low[MN],dfn[MN],f[MN];
vector<Edge> adj[MN],adj2[MN];
vector<int> vdcc[MN];
bool vis[MN];

void tarjan(int u){
    low[u]=dfn[u]=++tot;
    s[++top]=u;
    vis[u]=1;
    for(auto e:adj[u]){
        int v=e.v,w=e.w;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(vis[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        dcc++;
        int p;
        do
        {
            p=s[top--];
            color[p]=dcc;
            vdcc[dcc].push_back(p);
            vis[p]=0;
        } while (p!=u);
        
    }
}

void toposort(){
    queue<int> q;
    for(int i=1;i<=dcc;i++){
        if(!in[i]){
            q.push(i);
            f[i]=1;
        }
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(auto e:adj2[u]){
            in[e.v]--;
            f[e.v]=max(f[e.v],f[u]+e.w);
            if(!in[e.v]) q.push(e.v);
        }
    }
}

signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int mode,u,v;
        cin>>mode>>u>>v;
        if(mode==1){
            adj[v].push_back({u,0});
            adj[u].push_back({v,0});
            //cout<<u<<" "<<v<<" 0\n"<<v<<" "<<u<<" 0\n";
        }
        if(mode==2){
            adj[u].push_back({v,1});
            //cout<<u<<" "<<v<<" 1\n";
        }
        if(mode==3){
            adj[v].push_back({u,0});
            // cout<<u<<" "<<v<<" 0\n";
        }
        if(mode==4){
            adj[v].push_back({u,1});
            // cout<<v<<" "<<u<<" 1\n";
        }
        if(mode==5){
            adj[u].push_back({v,0});
            // cout<<u<<" "<<v<<" 0\n";
        }
    }
    //for(int i=1;i<=n;i++) adj[0].push_back({i,1});
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i);
    }
    for(int i=1;i<=n;i++){
        for(auto e:adj[i]){
            if(color[i]!=color[e.v]){
                adj2[color[i]].push_back({color[e.v],e.w});
                in[color[e.v]]++;
            }
            if(color[i]==color[e.v]&&e.w==1){
                cout<<-1;
                return 0;
            }
        }
    }
    toposort();
    int ans=0;
    for(int i=1;i<=dcc;i++){
        ans+=f[i]*vdcc[i].size();
    }
    cout<<ans;
    return 0;
}