wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

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

图论

图的连通性

有向图的强连通分量

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

流和匹配

最大流

最大流的一些应用

最小割

费用流

带上下界的网络流

二分图匹配

二分图最大权匹配

网络流综合

图论杂项

最大团搜索算法

树上问题

kruskal重构树

kruskal重构树的一些问题

最短路

差分约束

[[ item.c ]]

网络流综合

## ICPC Nanjing 2018 Magic Potion
**[I. Magic Potion](https://qoj.ac/contest/1832/problem/8979)**
给定`n`个英雄，有`m`个怪，每个英雄可以击杀其中的一些怪，每个英雄只能选择一个怪击杀
问最多能击杀多少个怪？
如果没有限制，就是二分图匹配，一个英雄只能被选一次，一个怪也只能被选一次

现在加了限制，有`k`瓶药水，可以分给英雄，**每个英雄最多一瓶药水**
英雄得到药水之后，可以多杀一个怪（一共可以杀`2`个怪）

问这个条件下，最多能击杀多少个怪？

**算法分析**
这是一个**分配问题**
对于怪来说，一个怪只能被杀一次，所以每个怪向`t`连流量上限是`1`的边
对于英雄，如果没有药水的情况下，一个英雄也只能被用一次，`s`向每个英雄连`1`的边

怎么表示**英雄得到药水呢？**
实际上要保证，**英雄得到药水之后，有`2`的流量**
也就是说，还必须有一条流量是`1`的边**指向英雄**

建一个“药水点”，这个药水点，向每个英雄连`1`的流量，从`s`向这个药水点连`k`的流量
然后从`s, t`跑最大流即可

## 圈地计划
**[圈地计划](https://www.luogu.com.cn/problem/P1935)**
给定$$n \times m$$个区域，每个区域$$(i, j)$$如果被改造成商业区，有$$A\_{i, j}$$价值
如果被改造成工业区，有$$B\_{i, j}$$的价值，同时，如果$$(i, j)$$相邻有$$k(k \leqslant 4)$$个不同的区域
那么会产生附加价值$$k\cdot C\_{i, j}$$，要求收益最大

**算法分析**
额外收益问题，回顾一下 **[Happiness](https://www.ringalgo.com/topic/72/)** 这个问题
选文科/选理科，看成是`S`集和`T`集，要求损失最小

首先一定有的收益就是`(s, x, 选文科收益)`，`(x, t, 选理科收益)`
额外收益怎么表示呢？**如果两个人同时在`S or T`集，才会产生这部分收益**
建一个辅助点，辅助点向这两个人连$$+\infty$$的边，然后`(s, 辅助点，额外收益)`

对上面的图求最小割

> 但是这个问题有所不同

之前的最小割问题，一个在`S`一个在`T`，那么`辅助点`$$\to$$`{u, v}`连$$+\infty$$的边
`S`$$\to$$`辅助点`连`额外代价`的边，表示**在不同集合，割开，会造成代价损失**
![](/media/content_img/luogu1935.png)

> 二分图棋盘染色

![](/media/content_img/luogu1935-02.png)

### 算法实现
> 建模方法

```bash
void solve() {
	// 其余代码省略
    // black and white
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) if ((i + j) % 2) swap(A[i][j], B[i][j]);
    }

maxflow<i64> g(N);

for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            auto u = ID[i][j];
            g.addEdge(s, u, A[i][j]);
            g.addEdge(u, t, B[i][j]);

tot += A[i][j], tot += B[i][j];
        }
    }

auto valid = [&](int x, int y) -> bool { return 1 <= x and x <= n and 1 <= y and y <= m; };
    const vector<int> dx = {-1, 0, 1, 0};
    const vector<int> dy = {0, -1, 0, 1};

for (int x = 1; x <= n; x++) {
        for (int y = 1; y <= m; y++) {
            auto u = ID[x][y];

for (int d = 0; d < 4; d++) {
                auto nx = x + dx[d], ny = y + dy[d];
                if (!valid(nx, ny)) continue;

auto v = ID[nx][ny];

idx++;
                g.addEdge(s, idx, C[x][y]);
                g.addEdge(idx, u, INF);
                g.addEdge(idx, v, INF);
                tot += C[x][y];

idx++;
                g.addEdge(idx, t, C[x][y]);
                g.addEdge(u, idx, INF);
                g.addEdge(v, idx, INF);
                tot += C[x][y];
            }
        }
    }

auto ans = tot - g.dinic(s, t);
    cout << ans << "\n";
}
```

## CCPC2019 Qinhuangdao
### E
**[Escape](https://codeforces.com/gym/102361)**
给定$$n \times m$$的矩阵，`0`表示可以通行，`1`表示不能通行
顶部有`a`个入口，底部有`b`个出口，在每个入口处放置一个机器人，让它们穿过矩形区域，
到达底部出口，机器人只能走直线，但可以放置转向器

每个格子只能放一个转向器，但每个格子可以同时存在多个机器人，问是否存在一种方式
使得所有机器人都能穿过矩形区域？

```bash
转向器类型
1）上-右 or 右-上
2）上-左 or 左-上
3）左-下 or 下-左
4）右-下 or 下-右

经过转向器，方向变化是都会执行的，比如放置转向器 1
原来是往上的，变成往右的，同时往右的，都变成往上的
```

**算法分析**
> 不存在两个机器人经过同个转向器之后，会走相同的方向

因为转向器**方向映射**是唯一的，`in -> out`，如果两个转向器`out`方向一致
说明他们的`in`方向也是一致的，这样的话，最开始两个转向器方向都应该一致，并且朝下走
也就是说，存在两个转向器一开始就在**同一个格子**中，而这是不可能的

> 路径模型

可以给每个起始位置`1`的流量，然后看一下最大流是否等于`n`，具体来说呢？

> 每个格子调整成，经过的机器人个数$$\leqslant 1$$个，一定可行

如果相向而行，画图（手模）之后，发现必然存在一个机器人**走回头路**
对于走回头路，路径自交的机器人，可以调整成一开始就走往下的路径

或者，根据上面的分析，每个格子，每个方向，在任何时刻都只有一个机器人
那么是不是可以考虑拆点？将方向也设计到状态中去，每个点机器人行走状态，分为**垂直，水平**
```bash
(i, j, 0) 表示在 (i, j) 这个位置，机器人垂直走向
(i, j, 1) 表示在 (i, j) 这个位置，机器人水平走向
```
**机器人不转向**
从左往右，`(i, j, 1) -> (i, j+1, 1)`，从右往左，`(i, j, 1) -> (i, j-1, 1)`
从上往下，`(i, j, 0) -> (i+1, j, 0)`，从下往上，`(i, j, 0) -> (i-1, j, 0)`

**机器人转向**
水平到垂直，`(i, j, 0) -> (i, j, 1)`
垂直到水平，`(i, j, 1) -> (i, j, 0)`

连边的时候，每个点的流量上限都是`1`
最后求`flow`的时候，`s`向**初始机器人位置（入口）**，`(1, j, 0) 垂直方向`连流量上限是`1`的边
同时**所有出口**`(n, j, 0) 垂直方向`向`t`连流量上限是`1`的边
求最大流，看一下是否等于机器人数量即可

> 算法实现

```bash
void solve(int cas) {
    int n, m, a, b;
    cin >> n >> m >> a >> b;

vector<string> grid(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> grid[i];
        grid[i] = " " + grid[i];
    }

int N = n * m * 2 + 10;
    int s = N - 3, t = s + 1;

maxflow<int> g(N);
    auto id = [&](int x, int y, int sgn) -> int {
        const int base = n * m;
        return (x - 1) * m + y + sgn * base;
    };

auto valid = [&](int x, int y) -> bool {
        if (not (1 <= x and x <= n and 1 <= y and y <= m)) return false;
        if (grid[x][y] == '1') return false;
        return true;
    };

for (int i = 0; i < a; i++) {
        int j;
        // [1, j, 0]
        cin >> j;
        auto x = id(1, j, 0);
        g.addEdge(s, x, 1);
    }

for (int i = 0; i < b; i++) {
        int j;
        cin >> j;
        auto x = id(n, j, 0);
        g.addEdge(x, t, 1);
    }
    // debug(g);

for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!valid(i, j)) continue;
            
            auto x = id(i, j, 0);
            
            // vertical
            if (valid(i+1, j)) {
                auto y = id(i+1, j, 0);
                g.addEdge(x, y, 1);
            }
            if (valid(i-1, j)) {
                auto y = id(i-1, j, 0);
                g.addEdge(x, y, 1);
            }

// horizon
            x = id(i, j, 1);
            if (valid(i, j+1)) {
                auto y = id(i, j+1, 1);
                g.addEdge(x, y, 1);
            }
            if (valid(i, j-1)) {
                auto y = id(i, j-1, 1);
                g.addEdge(x, y, 1);
            }

// trans
            auto u = id(i, j, 0), v = id(i, j, 1);
            g.addEdge(u, v, 1), g.addEdge(v, u, 1);
        }
    }

bool ok = g.dinic(s, t) == a;
    ok ? cout << "Yes\n" : cout << "No\n";
}
```
## 上下界最小费用可行流
**[SDOI2010 星际竞速](https://www.luogu.com.cn/problem/P2469)**
给定`n`个点，`m`条单向边（从编号小的连到编号大的），实际上是一个 DAG
希望访问`n`个点，每个点最多只能被访问一次

**每次操作，都要从起点出发**，起点和其他的点是不连通的
操作开始，你可以从起点花费`a[i]`的时间，瞬移到`i`号点

之后，假设说到达了$$u$$，可以沿着$$(u, v, w)$$花费$$w$$的时间到达`v`
当然，如果`w`太大的话，你也可以选择回到起点（不需要花费额外时间），然后从起点开始
花费$$a_v$$的代价直接跳到$$v$$，求访问完所有的点，需要的最小时间

**算法分析**
![](/media/content_img/SDOI2010-star01.png)

> 图论建模

怎么保证最少经过一次？比如`3`这个点至少要经过一次
那么从`in(3) -> tt`连的这条必须边，保证`3`一定会被访问一次
假如说有路径`x1 -> x2 -> ... -> xi -> 3`，一定会经过`out(xi) -> in(3)`
到达`in(3)`的时候可以直接流向`tt`，表示下界被满足了

另一方面，如果`3`可以被经过多次呢？之后`y1 -> y2 -> ... -> yi -> 3`
这个时候到达`out(yi) -> in(3)`之后就走不通了，怎么办？**考虑循环流**
那么这个时候`out(yi) -> 让它走到 t`，`t -> 通过循环流流回 s -> in(3) -> out(3)`
这样就保证了可以继续往下走

![](/media/content_img/SDOI2010-star02.png)

**算法实现**
```bash
MinCostFlow<i64> g(N);
for (int i = 1; i <= n; i++) {
	cin >> a[i];
	auto x = in(i), y = out(i);

g.addEdge(s, x, 1, a[i]);
	g.addEdge(y, t, inf<i64>, 0);
}
for (int i = 1; i <= m; i++) {
	int u, v;
	i64 w;
	cin >> u >> v >> w;

if (u > v) swap(u, v);
	g.addEdge(out(u), in(v), 1, w);
}
// 超级源汇，保证流量下界，每个点都必须至少经过 1 次
for (int i = 1; i <= n; i++) {
	auto x = in(i), y = out(i);
	g.addEdge(ss, y, 1, 0);
	g.addEdge(x, tt, 1, 0);
}
// 循环流
g.addEdge(t, s, inf<i64>, 0);
```
## 路径模型
**[ZJOI2011 营救皮卡丘](https://www.luogu.com.cn/problem/P4542)**
给定`n`个点`m`条无向边的图，起点是`0`，据点编号是$$1 \sim n$$
有`k`个人从`0`号起点出发，你要想进入据点`x`，必须保证$$1 \sim x - 1$$据点都被清空
任何一个人经过据点`x`，都可以被认为据点被摧毁，据点被摧毁之后，还是可以重复经过的

当然，据点`x`被摧毁，当且仅当存在一个人，在据点`[1, x-1]`都被摧毁后，这个人接着经过据点`x`

现在目标是摧毁据点`n`，需要最小化`k`个人经过的路径总和

**算法分析**
> 如果没有访问`x`必须先依次访问`[1...x-1]`的限制，怎么做？

起点`0`可以向`点 1`连流量上限是`k`，费用是`0`的边
对于点$$u$$，它必须经过至少一次，那么`in(u) -> out(u)`连流量$$[1, +\infty)$$的边
费用是`0`，因为双向边，$$(u, v), (v, u)$$都要连边

但这样做是错的，因为如果$$x \to x+1$$，有可能从`s -> x+1 甚至更大的点 -> 绕行回 x`
这样是不合法的

> 只连$$u < v$$的边可不可以？

也是不可以的，比如$$u \to y$$，此时如果$$u$$之前的某个点`p`被摧毁了
那么$$u \to p$$先往前走，然后$$p \to y$$这样可能会更优

![](/media/content_img/ZJOI2011.png)

> 特别说明

这里的`dis(x, y)`要求$$x \to y$$**并且不能经过比`y`编号大的中间节点**
如果直接`floyd`用`dis(x, y)`，求出的是全源最短路，中间是可能经过编号$$> y$$的点的

正确的做法是，一边`floyd`一边维护答案，`floyd`动态规划就是以**节点编号**作为`dp`的阶段
最外层的`for k = 1 to n`，实际上就表示**全源最短路，只会经过编号**$$\leqslant k$$**的节点**
将此时的$$dis(x, k) \to ret(x, k)$$，缓存下来，最后用`ret(x, y)`来加边计算

## 最小割问题
**[AHOI2009 最小割](https://www.luogu.com.cn/problem/P4126)**
给定`n`个点`m`条**单向边**的图，其中边$$(u_i, v_i)$$，如果切断这条边，需要$$c_i$$的代价
现在要切断路径，使得$$s$$不能够到达$$t$$，要求切断路径的代价之和最小

这是一个最小割问题，现在对每条单向道路问两个问题
问题一，是否存在一个最小代价路径切段方案，使得这条道路被切断
问题二，是否对任何一个最小代价路径切段方案，该条道路都会被切断

换句话说，判断每条边，是不是可能在最小割里，会不会一定在最小割里

**算法分析**
> 先看第二问

如果暴力的话，就把这条边删掉，然后重新跑一遍最小割，看看最小割会不会变
换句话说，我们需要强制这条边不在最小割中，怎么强制呢？将边权设置成$$+\infty$$
然后再跑一遍最大流，看看流会不会变

具体来说，需要$$u \to v$$连$$+\infty$$的边，再计算一遍最小割

> 再看第一问

第一问暴力做法，怎么强制让一条边在割中？对于这条边$$(u, v)$$，相当于$$u$$一定要在$$S$$集中
同时，$$v$$一定要在$$T$$集中，只需要$$s \to u$$连$$+\infty$$的边，$$v \to t$$连$$+\infty$$的边
然后计算最小割，看一下会不会变

> 考虑优化

跑完最大流之后的残量网络，本来$$s, t$$是不连通的
**第一问，什么时候**$$(u, v)$$**可能在最小割中？**
就是强制让`u`在$$S$$集，`v`在$$T$$集，看一下$$s, t$$是否还是不连通的，如果仍然不连通
那么就可以在最小割中

**第二问，什么时候**$$(u, v)$$**一定在最小割中？**
实际上就是“没它不行”，这怎么做呢？如果强制让$$(u, v)$$**割不开**，$$s, t$$就连通了
这时候$$(u, v)$$就一定在最小割中

基于上面的分析
发现第二问，求完最大流之后，只需要判断$$s \to u$$是否可达，$$v \to t$$是否可达
这可以用**残量网络**直接求出，残量网络`bfs`，如果$$h_u \neq -1$$，说明$$u$$从$$S$$可达
也就是说$$u$$在$$S$$集中

对于$$t$$呢，也是一样的，残量网络有反向边嘛，从$$t$$开始`bfs`
那么实际上，对于边$$i$$，实际上是反向边$$t \to v$$，那么原来的正向边呢？
比如$$v \to t$$，对应边$$e[i \oplus 1]$$，如果`cap > 0`，说明还有残余流量
那么此时$$v$$可达$$t$$，也就是`minCut`可以求出来

那么对于第一问，怎么判断$$s \to t$$是否连通
因为我们强制地让`u`在$$S$$集，`v`在$$T$$集，如果$$(u, v)$$的`flow > 0`
说明`s -> t`是连通的，那么这条边就不在最小割中

如果$$(u, v)$$的`flow = 0`呢？`s -> u, v -> t`是我们强制加的
此时$$u$$能否到达$$v$$呢？**残量网络有什么性质？**
注意到`(u, v) flow = 0`，说明一定存在反向边$$v \to u$$，判断$$u$$能否到达$$v$$
实际上**考虑残量网络，判断$$u, v$$是否在同一个 SCC 中**

### 算法实现
```bash
void solve(int cas) {
    g.dinic(s, t);
	// 计算从 s 可达的点
	// 计算可达 t 的点
    auto belS = g.minCut();
    auto belT = g.minCut2(s, t);

SCC scc(N);
    for (int i = 0; i < g.e.size(); i += 2) {
        auto [v, rflow] = g.e[i];
        auto [u, flow] = g.e[i ^ 1];

if (rflow > 0) scc.addEdge(u, v);
        if (flow > 0) scc.addEdge(v, u);
    }

scc.work();
    for (int i = 0; i < g.e.size(); i += 2) {
        auto [v, rflow] = g.e[i];
        auto [u, flow] = g.e[i ^ 1];
		
		// 原始最小割中，u, v 还没有断开，那么它就不是割边
        if (rflow > 0) {
            ans1.emplace_back(0), ans2.emplace_back(0);
            continue;
        }
		
		// 如果是割边，且 u, v 断开，但是 u 有可能通过其他方式和 v 连通
		// 此时我们仍认为 u, v 没有真正意义上的断开，这条边就不是真正意义上的割边
		// 判断 u, v 能不能以其他路径连通，就看 u, v 是否在同一个 SCC 中
        int res1 = scc.bel[u] != scc.bel[v];
		
		// 强制加上这条边 s，t 就连通了，所以它必须断开
        int res2 = (belS[u] == 1 and belT[v] == 1);

ans1.emplace_back(res1), ans2.emplace_back(res2);
    }

for (int i = 0; i < m; i++) {
        cout << ans1[i] << " " << ans2[i] << "\n";
    }
}
```

看完文章有啥想法

算法小站

wiki 主题

图论

网络流综合

目录