wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

图论

图的连通性

有向图的强连通分量

无向图的割点割边和双连通分量

流和匹配

最大流

最大流的一些应用

最小割

费用流

图论杂项

最大团搜索算法

树上问题

kruskal重构树

kruskal重构树的一些问题

最短路

差分约束

[[ item.c ]]

差分约束

## 差分约束问题
给定一组$$\left< x_1, x_2, \cdots, x_n \right>$$，给定若干限制，形如$$x_i - x_j \leqslant C$$
然后判定原来的问题有解，还是无解

如果是$$x_i - x_j \geqslant C$$，那么问题转化成$$x_j - x_i \leqslant -C$$

如果是$$x_i - x_j = C$$呢，那么拆成
```math
\displaystyle
\begin{cases}
x_i - x_j \leqslant C \\
x_i - x_j \geqslant C
\end{cases} \Rightarrow

\begin{cases}
x_i - x_j \leqslant C \\
x_j - x_i \leqslant -C
\end{cases}
```

## 差分约束系统
给定$$m$$个不等式，有$$n$$个未知数，形如
```math
\displaystyle
\begin{cases}
x_{c_1} - x_{c_1'} \leqslant y_1 \\
x_{c_2} - x_{c_2'} \leqslant y_2 \\
\cdots \\
x_{c_m} - x_{c_m'} \leqslant y_m
\end{cases}
```
求满足这个不等式组的非负解，并且使得每个变量尽可能小

**算法分析**
考虑**调整**值，比如$$(x_1, x_2, x_3)$$
```math
\displaystyle
\begin{cases}
x_1 \leqslant x_2 + 3 \\
x_2 \leqslant x_3 - 2 \\
x_1 \leqslant x_3 + 1
\end{cases}
```
一开始令$$(x_1, x_2, x_3) = (0, 0, 0)$$，之后我们发现$$x_2 \leqslant x_3 - 2$$不满足约束
那么调整，令$$(0, 0, 0) \to (0, -2, 0)$$

注意到，将方程写成$$x_v \leqslant x_u + w $$的形式，去`for 所有的限制 (u, v, w)`
如果发现$$x_v > x_u + w$$，那么就让$$x_v = \min(x_v, x_u + w)$$
不停调整，直到满足为止

> 正确性？时间复杂度呢？

注意到$$x_v \leqslant x_u + w$$，这样的不等式组和**Bellman-Ford 三角不等式**是一模一样的
回顾`Bellman-Ford 算法`，`for 每条边 (u, v, w)`，只要**不满足**$$dis_v \leqslant dis_u + w$$
就**不断迭代**

所以差分约束实际上就是执行 Bellman-Ford

> 负环呢？负环对应差分约束无解

```math
\displaystyle
\begin{cases}
b \leqslant a + (-1) \\
c \leqslant b + (-1) \\
d \leqslant c + (-1) \\
a \leqslant d + (-1)
\end{cases}
```
那么不等式两边加起来，有`0 <= 负环的总长度`，这是不可能的

> 算法实现

对于每一条限制$$x_v \leqslant x_u + w$$，对$$u \to v$$，连一条边权是$$w$$的边
跑一遍最短路，那么$$x_i = d_i$$就对应原来问题的一组**合法的解**

> 怎么求非负解

注意到，如果我们求解出$$x_1, x_2, \cdots x_n$$
那么根据差分约束形式$$x_i - x_j \leqslant c_k$$，将$$x_i, x_j$$都`+d`也是合法的解

单个变量可能有额外的限制，比如$$x_j \leqslant C, x_j \geqslant 0$$之类的

那么这种情况，可以引入一个**基准变量**$$x_0$$，所有值都加上这个基准值$$x_0$$，即$$x_i' = x_i + x_0$$
那么单个变量的限制可以写成
```math
\displaystyle
\begin{cases}
x_j = x_j' - x_0 \leqslant C \\
x_j' - x_0 \geqslant 0
\end{cases}
```
这样仍可以用差分约束系统求解，添加边$$(j, 0, 0)$$，然后求解最短路
只不过这时候求出的最短路$$dis_i = x_i'$$，最后要令$$x_i' - x_0$$才是真正的值

> 怎么让每个变量尽量小？

注意到`Bellman-Ford`算法求出来的是**最大合法解**
```math
\displaystyle
\begin{cases}
x_1 \leqslant s + w_1 \\
x_2 \leqslant x_1 + w_2 \\
\cdots \\
x_k \leqslant x_{k-1} + w_k
\end{cases}
```
将不等式代入之后发现，$$x_k \leqslant s + (w_1 + w_2 + \cdots + w_k)$$
这是最紧的限制，对应的是$$x_k$$的最大解

最小值怎么办呢？对于$$x_u - x_v \leqslant w$$，可以令$$x_u' = -x_u$$
那么有$$(-x_u') - (-x_v') \leqslant w$$，也就是$$x_v' \leqslant x_u' + w$$

同样差分约束求解，求解完之后，注意到之前求出来的值是$$x_i' = dis_i - x_0$$
最后真正的值还要取反一下，是$$x_0 - dis_i$$

> 综上所述

1）怎么保证让**每个变量尽量小？**
令$$x_u' = -x_u$$，这样，每一个约束写成
```math
\displaystyle
(-x_u') - (-x_v') \leqslant y \\
\Rightarrow x_v' \leqslant x_u' + y \\
\text{addEdge }(u \to v, y)
```
2）怎么保证每个变量非负？
即保证$$(-x_u') \geqslant 0 \Rightarrow x_u' \leqslant 0$$
令$$x_u' = x_u'' - x_0$$，那么$$x_u'' \leqslant x_0 + 0$$

最后差分约束求最短路，对应求出$$x_u' = x_u'' - x_0 = dis_u - dis_0$$
真正的值$$x_u = -x_u'$$，也就是$$x_u = dis_0 - dis_u$$

```bash
void calc() {
    Graph<i64> g(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        i64 y;
        cin >> u >> v >> y;
        g.addEdge(u, v, y);
    }
    for (int u = 1; u <= n; u++) {
        g.addEdge(0, u, 0);
    }

bool sgn = g.spfa(0);

if (!sgn) {
        cout << "-1\n";
        return;
    }
    vector<int> X(n+1, 0);
    for (int i = 1; i <= n; i++) X[i] = g.dis[0] - g.dis[i];
}
```

## 糖果
**[SCOI2011 糖果](https://www.luogu.com.cn/problem/P3275)**
给定几个需求，求满足这些需求，并且$$x$$要尽量小（最小值根据 Bellman-Ford 三角不等式，边反过来连）
1）$$x_a = x_b$$，实际上是$$x_a \leqslant x_b, x_b \leqslant x_a$$
2）$$x_a < x_b$$，实际上是$$x_a - x_b \leqslant -1$$
3）$$x_a \geqslant x_b$$，实际上是$$x_b - x_a \leqslant 0$$
4）$$x_a > x_b$$，实际上是$$x_b - x_a \leqslant -1$$
5）$$x_a \leqslant x_b$$，实际上就是$$x_a - x_b \leqslant 0$$

另外还需要非负，所以$$x_a \geqslant 0$$

构建差分约束系统来求解

**算法分析**
1）对于每个约束，因为要求最小值，令$$x_j' = -x_j$$，对于$$x_a - x_b \leqslant C$$
连边$$(a \to b,  C)$$

2）另外$$x_a \geqslant 1$$，实际上相当于$$x_a' \leqslant -1$$，差分约束添加一个基准
令$$x_a^{\prime} = x_a^{\prime \prime} - x_0 \leqslant -1$$，考虑连边$$(0 \to a, -1)$$

差分约束，跑最短路，求出$$x_a^{\prime \prime} = dis_a$$，实际上的解$$x_a = dis_0 - dis_a$$

## POI2012 Festival
**[POI 2012 FES-Festival](https://www.luogu.com.cn/problem/P3530)**
给定`n`个限制，$$(a, b)$$表示$$x_a = x_b - 1$$，而$$(c, d)$$表示$$x_c \leqslant x_d$$
问符合限制的值有多少种？

（他们中的一些人可能平局，也就是同时到达终点，这种情况只算有一种成绩）
也就是说，我们关心不同人之间，成绩的相对大小关系有多少种，而不关心具体的成绩

换句话说，**只要值域能错开，尽量错开**

**算法分析**
> 判断有没有解很简单，求解差分约束，最短路，判负环即可，现在的问题是，要求符合条件的有多少种
而 spfa 只能求出**最大/最小**的合法解，怎么办呢？

注意到，这些限制$$x_a = x_b = 1$$，会添加两条边$$\pm 1$$，还有一种情况是边权是$$0$$的边
如果不同人之间已经通过$$\pm 1$$的边连起来了，或者通过$$0$$的边连起来了
那么这样的人之间，它的**相对大小关系**是确定的，大小**不可能无限拉大**

> 两个联通块之间没有关系，令他们的**值域尽量错开**，错开越大越好
如果两个点相互可达（在**同一个 SCC **中），那么这两个点之间的差值是**不能无限大的**

证明其实并不难
```math
\displaystyle
\begin{cases}
d_v \leqslant d_u + x_1 \\
d_u \leqslant d_v + x_2 
\end{cases} \Rightarrow d_u - x_2 \leqslant d_v \leqslant d_u + x_1
```
但假如说只有$$d_v \leqslant d_u + x_1$$，$$d_v$$可以任意小

每个强连通分量之间的大小关系是有限的，可以考虑对每个 SCC 分开来单独考虑
然后最后把每个 SCC 答案加起来

**强连通分量之间，值域可以不相交**，每部分答案必然可以错开

> 强连通分量，内部有多少种取值

注意到**边权如果只有**$$\pm 1$$的话，意味着**最小值和最大值之间是连续出现的**
比如最小值是`-4`，最大值是`7`，`[-4, -3, -2, ..., 6, 7]`这些数都是存在的
（否则的话，合法解一部分$$< 0$$，一部分$$> 0$$，$$< 0$$和$$> 0$$部分只有$$<$$关系，不强连通，矛盾）

**边权是`0, 1, -1`，每个`SCC`取值连续**

> 问题转化成，对于每个`SCC`，$$\max - \min$$**尽可能大**

一种想法是，对于每个点可能的$$\max$$，实际上跑一遍最短路就可以求出来
因为三角不等式$$x_a \leqslant x_b + w$$，求出来$$x_a = dis_a$$就是$$a$$这个点能取到的最大值

那么我们可以枚举哪个是`min`，也就是**对每个`SCC`，枚举起点`u`，跑一遍多源最短路**
求最大的$$\max_v dis(u, v)$$即可

技巧，如果是`Floyd-Warshall`算法，`SCC`不要用 Tarjan 直接算了
如果距离初始值是$$+\infty$$，对于每个点$$u$$，只要把$$dis(u, v) \neq +\infty, dis(v, u) \neq +\infty$$
实际上就表示了这两个点**相互可达**

> `Floyd-Warshall`算法，判负环怎么判呢？实际上也不难，`dis[i][i] < 0`那么就有负环

> `Floyd-Warshall`算法，怎么求`SCC`呢？枚举每个点$$i$$，如果$$i$$没有被检查过
再枚举每一个$$j$$，如果$$(i, j)$$可达`dis(i, j) <= n+1`，那么`SCC.emplace_back(j)`
最后暴力每一个强连通分量`SCC`中的`dis(x, y)`，将极差加入答案中

### 算法实现
```bash
auto mat = FloydWarshall(g);

void calc() {
    // Floyd 求负环
    for (int u = 1; u <= n; u++) {
        if (mat[u][u] < 0) {
            cout << "-1\n";
            return;
        }
    }

// Floyd 求 SCC，不要用 tarjan 那么麻烦
    vector<int> done(n+5, 0);
    int ans = 0;
	
    for (int x = 1; x <= n; x++) if (!done[x]) {
        vector<int> scc;
        for (int y = 1; y <= n; y++) {
            if (!done[y] and mat[x][y] <= n+1 and mat[y][x] <= n+1) {
                scc.emplace_back(y);
                done[y] = 1;
            }
        }

// 求出每个 scc 中的最长距离
        int res = 0;
        for (auto x : scc) for (auto y : scc) {
            chmax(res, mat[x][y]);
        }
		ans += res + 1;
    }
}
```
## Tenzing and His Animal Friends
**[D. Tenzing and His Animal Friends](https://codeforces.com/contest/1842/problem/D)**
`n`个人，其中`1`必须参加聚会，`n`必须不能参加聚会，有`m`个限制$$(u, v, y)$$
表示`u`一个人参加聚会的次数，和`v`一个人参加聚会的次数，这两个值，有且只能有一个$$\leqslant y$$

换句话说，假设说$$t_u$$是$$u$$总共的参会时间，那么对每个限制$$|t_u - t_v| \leqslant y$$

**算法分析**
> 看完简化版题意，这个问题有点像**差分约束**

首先来分析一下，`1`一定要参会，`n`一定不能参会，这里有什么性质？
根据差分约束，$$|t_u - t_v| \leqslant y$$，`n`不能参会，那么$$t_n = 0$$

> 先考虑$$(n, u, y_1)$$，然后再看$$u$$相连的点$$(u, v_1, y_2), (u, v_2, y_3), \cdots$$

不难发现需要满足的条件是，对于`u`，一定要有的是$$t_u \leqslant y_1 \Rightarrow t_u \leqslant 0 + y_1$$
实际上是$$t_u \leqslant t_n + y_1$$

然后呢，对于$$(u, v\_1)$$，我们让他们尽可能一起参会是划算的，如果分开的话，只会导致一个人参会时间被拉大
一起参会的话，共同参会的总时间就增加了（二者共同参会的话，就没有特别额外限制了）
我们又有$$t(v_1) \leqslant t(u) + y_2$$，以此类推

这是什么？**Bellman-Ford 最短路三角不等式**
也就是说，最后的$$t(u)$$，恰好是以`n`为源点，跑最短路得到的$$dis_u$$

因为`1`每次都要参会，所以`1`参会的总时间，实际上就是活动举办的总时间
这个总时间$$=t(1) = dis(1)$$

如果$$dis(1) = +\infty$$，意味着游戏可以无限进行下去，实际上也确实如此，因为这个题目有一个比较有意思的地方
**只要是在一起玩，那么这部分公共的时间是没有限制的**，类似这样的问题，都可能可以用**差分约束**来刻画

> 怎么去构造？

有一个很显然的贪心，就是随着时间的进行，**要带着尽可能多的动物一起玩**
如果从`n`开始看，对于$$(n, u)$$这条边，实际上是有最强的限制的
也就是说，**`u`脱离`n 这个集合`最长的时间**必须$$\leqslant dis(1, n) - dis(1, u)$$

同时考虑$$(u, v)$$，不难发现，$$u$$**不带**$$v$$一起玩的时间最多只能是$$dis(1, u) - dis(1, v)$$

换句话说，不难发现随着时间的进行，`1`会带着**越来越多的动物一起玩**
对于边$$(u, v)$$，$$u$$脱离$$v$$，加入`1 这个一起玩的集合`的时间，最多只能是$$dis(1, v) - dis(1, u)$$
之后就要立刻带上`v`一起玩了

那么考虑**什么时候加入“一起玩的集合”**，不难发现，对于$$(u, n)$$，$$u$$必须最晚加入这个一起玩集合
而第二晚的呢？就是$$(v, u), v$$这个点了，先带`v`玩够$$dis(1, u) - dis(1, v)$$之后，再捎上`u`一起玩

综上所述，可以考虑根据$$dis(1, u)$$对每个`dis`排序去重，得到一个时间戳集合`t`
构造的时候，从小到大`for t[i]`，如果$$dis(1, u) \leqslant t_i$$，那么把`u 加入一起玩集合`
玩多长时间呢？只能是$$t(i+1) - t(i)$$，接下来就应该考虑带上$$t(i+1)$$的哪些点了

### 算法实现
```bash
void solve(int cas) {
    int n, m;
    cin >> n >> m;

Graph<i64> g(n);

for (int i = 0; i < m; i++) {
        int x, y;
        i64 z;
        cin >> x >> y >> z;
        g.addEdge(x, y, z), g.addEdge(y, x, z);
    }

auto mat = FloydWarshall(g);

if (mat[n][1] >= inf<i64>) {
        cout << "inf\n";
        return;
    }
    cout << mat[n][1] << " ";

vector<i64> t;
    for (int u = 1; u <= n; u++) if (mat[1][u] <= mat[1][n]) {
        t.emplace_back(mat[1][u]);
    }

sort(t.begin(), t.end());
    t.erase(unique(t.begin(), t.end()), t.end());

cout << t.size() - 1 << "\n";

auto out = [&](const vector<int> &res) -> void {
        for (int i = 1; i <= n; i++) cout << res[i];
    };

for (int i = 0; i + 1 < t.size(); i++) {
        auto tx = t[i];
        auto dt = t[i+1] - t[i];

vector<int> res(n+1, 0);

for (int x = 1; x < n; x++) if (mat[1][x] <= tx) res[x] = 1;

out(res);
        cout << " " << dt << "\n";
    }
}
```

## 最大子段和
**[最大子段和](https://pintia.cn/problem-sets/1547474014070099968/exam/problems/type/7?problemSetProblemId=1556536449770938368)**
定义一个序列`a[1...n]`的最大子段和$$\max(0, \max\_{1 \leqslant l \leqslant r \leqslant n} \sum\_{i = l}^{r}a\_i)$$

现在我们有一个整数序列`b[1...n]`，会告诉你每个$$1 \leqslant l \leqslant r \leqslant n, \  b[l, r]$$
的最大子段和$$mss\_{l, r}$$

找到一个满足条件的`b[1...n]`

**算法分析**
> 一个很重要的关系

```math
mss_{l, r} = \max(mss_{l+1, r}, mss_{l, r-1}, \sum_{l, r}) \\
= \max(mss_{l+1, r}, mss_{l, r-1}, (S_r - S_{l-1}))
```
其中只有$$S\_r, S\_{l-1}$$是我们不知道的

> 考虑分类讨论，情况一

如果$$mss\_{l, r} = \max(mss\_{l+1, r}, mss\_{l, r-1})$$，此时只需要$$S\_r \leqslant S\_{l-1} + mss\_{l, r}$$

> 情况二

如果$$mss\_{l, r} > \max(mss\_{l-1}, r, mss\_{l, r-1})$$，那么一定有$$mss\_{l, r} = S\_r - S\_{l-1}$$
也就是说
```math
\displaystyle
\begin{cases}
S_{l-1} \leqslant S_r - mss_{l, r} \\
S_r \leqslant S_{l-1} + mss_{l, r}
\end{cases}
```
以上都可以用差分约束求出合法的$$S$$，进而得到答案

> 关于$$S_0 = 0$$怎么处理？

在一般的问题中，需要建立一个虚点，将每个值都平移一个单位
```math
\begin{cases}
S_i = S_i' - S_{NIL} \leqslant 0 \Rightarrow S_i' \leqslant S_{NIL} + 0 \\
S_{NIL} \leqslant S_i' + (-0)
\end{cases}
```
可以令$$S\_{NIL}$$强行为`0`，也就是从`NIL`为**源点**，跑最短路

但是这个问题中，**保证有解**
也就是说，实际上以`0`为**源点**，跑最短路，$$S_0 = dis_0 = 0$$，即可保证`S[0] = 0`

### 算法实现
```bash
void solve(int cas) {
    int n;
    cin >> n;

vector mss(n+5, vector<i64>(n+5, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            cin >> mss[i][j];
        }
    }

// debug(mss);
    Graph<i64> g(n);

for (int l = 1; l <= n; l++) {
        for (int r = l; r <= n; r++) {
            if (mss[l][r] == max(mss[l+1][r], mss[l][r-1])) {
                g.addEdge(l-1, r, mss[l][r]);
            }
            else if (mss[l][r] > max(mss[l+1][r], mss[l][r-1])) {
                g.addEdge(r, l-1, -mss[l][r]);
                g.addEdge(l-1, r, mss[l][r]);
            }
        }
    }

g.spfa(0);

auto S = g.dis;

vector<i64> b(n+1, 0);
    for (int i = 1; i <= n; i++) b[i] = S[i] - S[i-1];

for (int i = 1; i <= n; i++) cout << b[i] << " ";
    cout << "\n";
}
```

看完文章有啥想法

算法小站

wiki 主题

图论

差分约束

目录