wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

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

图论

图的连通性

有向图的强连通分量

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

流和匹配

最大流

最大流的一些应用

最小割

费用流

图论杂项

最大团搜索算法

树上问题

kruskal重构树

kruskal重构树的一些问题

[[ item.c ]]

最小割及应用

## 最小割的定义
![](/media/content_img/mincut01.png)

**割边**
对于有向边$$(u, v)$$，如果$$u \in S, v \in T$$，这样的边叫做割边

最小割，就是使得$$\displaystyle \sum\_{u \in S, v \in T} c(u, v)$$ 最小的边集

如果是无向边$$(u, v)$$，当`u, v`不属于同一个集合，被视为割边

**最大流最小割定理**
```math
mincnt \geqslant maxflow
```

## 割集
**注意**，割集中的边流量一定是`0`，但流量为`0`的边不一定属于割集
怎么求割集呢？

跑完最大流之后，对残量网络进行`bfs`，从起点`s`沿着流量`> 0`的边走，能到达的点$$\in S$$集
剩下的点$$\in T$$集

根据割边的定义，对于每一条边$$(u, v)$$，只要$$u \in S, v \in T$$，它就是割边

### 割集的变种
**最大割**
对每个点标记，这个点$$\in S$$还是$$\in T$$，然后考虑割边$$(u, v), u \in S, v \in T$$
使得割边的$$\sum c(u, v)$$最大

相当于边权为负的最小割，这个问题是`NP-complete`的，只有指数算法

**无向图的全局最小割**
比如说 tarjan 算法中的割边，就可以认为是**大小为`1`的割**
最暴力的解法是，枚举起点`s`和终点`t`，跑一遍最小割，对这样的割集大小，全局取一个`min`

## 最小生成树
**[最小生成树](https://ac.nowcoder.com/acm/problem/212292)**
给定一个`(n, m)`的，边权为正的无向连通图，再给定`(u, v, L)`三个数
问假设现在加入边`(u, v, L)`，需要删除多少条边，才能使得这条边既可能出现在最小生成树上
又可能出现在最大生成树上？

**算法分析**
> 先用 kruskal 算法来思考

假设要加入边$$(u, v, L)$$，那么什么时候它会出现在最小生成树中呢？
从小到大加边，如果把$$< L$$的边都加入了，$$(u, v)$$仍然不连通，那么这条边就会出现在最小生成树中
同样，把$$> L$$的边都加入了，$$(u, v)$$仍然不连通，那么这条边就会出现在最大生成树中

考虑`< L`的边使得`(u, v)`不连通，同时考虑`> L`的边使得`(u, v)`不连通
剩下的边都可以删掉

换句话说，这个问题就是在`< L`的边集中，删一些边，使得`(u, v)`不连通
同时在`> L`的边集中，再做一遍

两个部分是独立的，对于`(u, v, L)`，求`u, v`的最小割
1）只加入`< L`的那些边，跑一遍最小割，`dinic(u, v)`
2）然后再加入`> L`的那些边，再跑一遍最小割，`dinic(u, v)`
两部分加起来就是答案

## Builder Takahashi
**[G - Builder Takahashi](https://atcoder.jp/contests/abc239/tasks/abc239_g)**
给定一个`(n, m)`的无向连通图，要求在某些点设置障碍，但是不能在`1`号或者`n`号点设置
在$$i$$号点设置障碍的费用是$$c_i$$，要使得`1`号点和`n`号点不连通，问最小的花费

**算法分析**
考虑拆点，将$$u$$拆成$$(u, u+n, c_u)$$，表示`u 向 u+n`连一条流量上限是$$c_u$$的边
至于原来边呢？$$(u, v)$$，我们设置$$(u, v, +\infty)$$，流量上限是$$+\infty$$的边
实际上表示**这些边是割不开的**

考虑到我们拆点，$$(u, v)$$实际上对应$$(n+u, v, +\infty), (n+v, u, +\infty)$$这两条边
当然`1, n`我们不拆，（当然为了好写，也可以拆点，只不过边设置为$$(1, 1+n, +\infty)$$），这样就割不开了
最后令`s = 2n+1, t = 2n+2`，跑一遍`dinic(s, t)`

输出方案呢？跑一遍`bfs`，给每个点编号`S`集还是`T`集，取$$u \in S, v \in T$$的边即可

## 方格取数
**[网络流24题 - 方格取数问题](https://ac.nowcoder.com/acm/problem/213822)**
给定$$m \times n$$的方格，每个方格中有一个正整数
从方格中取数，使得任意两个数所在的方格没有公共边，并且取出的数的总和最大，求最大的和

**二分图最大权独立集**
网格图显然是一个二分图，这个问题实际上是求二分图最大权独立集
（注意，普通的最大权独立集问题，是`NPC`的，没有多项式算法）

> 怎么求二分图最大权独立集

对于边$$(u, v)$$，独立集要求$$(u, v)$$不能同时被选，必须删除一个
```bash
最大权独立集 = 总的 - min(没有被选进来的点)
```
接着考虑**什么样的点才是没有被选进来？**
凡是被选中的点有什么特征？比如`u`被选中，那么就意味着$$(u, v)$$必须断开
没有被选中，就意味着$$\\{u, v\\}$$同时$$\in S$$集，或者$$\\{u, v\\}$$同时$$\in T$$集

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

算法实现上，因为网格图是二分图，$$(i, j)$$可以用$$(i+j) \bmod 2$$来判断是左边的点还是右边的点
（二分图有两排的点）

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

int N = n * m + 2;
    maxflow<i64> g(N+5);

int s = n * m + 1, t = n * m + 2;

i64 ans = 0;

for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            i64 x;
            cin >> x;
            ans += x;
            int id = (i - 1) * m + j;

if ((i + j) % 2 == 0) {
                g.addEdge(s, id, x);
    
                if (i - 1 >= 1) g.addEdge(id, id-m, inf<i64>);
                if (i + 1 <= n) g.addEdge(id, id+m, inf<i64>);
                if (j - 1 >= 1) g.addEdge(id, id-1, inf<i64>);
                if (j + 1 <= m) g.addEdge(id, id+1, inf<i64>);
            }
            else {
                g.addEdge(id, t, x);
            }
        }
    }

ans -= g.dinic(s, t);
    cout << ans << "\n";
}
```
## 最大权闭合子图
**[网络流24题 - 太空飞行计划问题](https://ac.nowcoder.com/acm/problem/213816)**
给定一个实验集合$$\\{E_1, E_2,\cdots, E_m\\}$$，给定进行实验所需要的所有仪器的集合$$\\{I_1, I_2, \cdots, I_n\\}$$
实验$$E_j$$所用到的仪器集合$$R$$是$$I$$的**子集**
其中仪器$$I_k$$花费$$c_k$$美元，同时实验$$E_j$$的利润是$$p_j$$元，要求净收益最大
仪器是可以重复使用的

> 最大权闭合子图

给定一些点，点权可以`+`也可以`-`，同时点之间有**依赖关系**
依赖关系用$$u \to v$$的**有向边**表示

现在要选一些点，使得点权和最大
同时还有限制，如果一个点选了，那么它的**后继节点都必须要选**
这样的问题，被称为最大权闭合子图问题

太空飞行计划问题，可以看作**最大权闭合子图**问题
相当于两排点，左边一排表示实验，实验的价值都是`+`的
右边一排表示仪器，仪器的价值是`-`的，考虑实验和仪器连边

> 考虑最大权闭合子图的解法

```bash
权值 > 0 的点都选进来 - min( 损失 )
```
于是需要最小化$$\min ( \sum loss )$$，最小化损失
损失包括两个部分
1）选了一些权值$$< 0$$的点
2）没有选中一些$$> 0$$的点

> 考虑最小割建模的意义

划分为$$S$$集和$$T$$集，考虑每个点`u`被分到`S`集还是`T`集中
1）如果$$u \in S$$，表示$$u$$**被选了**
2）如果$$u \in T$$，表示$$u$$**未被选中**

然后对每个点考虑损失，怎么去表示损失？
1）正权点，如果没有选，那么损失是$$a_u$$，什么情况下是没有选呢？
那就是它属于$$T$$集，$$(s, u)$$连一条流量上限是$$a_u$$的边
没有选，造成的损失，相当于将`u`放入`T`集中，也就意味着**割掉这条边**

2）负权点，如果它被选了，在$$S$$集中，会产生$$|a_u|$$的损失
将$$(u, t)$$连边，流量上限是$$|a_u|$$

那么对于依赖关系，$$(u, v)$$表示$$u \to v$$，`u`在`S`集中，`v`也必须在`S`集中
也就是说，$$(u, v)$$这条边**割不掉**，流量设置为$$+\infty$$

跑一遍最小割，$$(\sum [> 0]) - dinic(s, t)$$就是答案、
输出方案，就看一个点在`S`集中，说明这个点被选了，否则说明没有选

## Happiness
**[Happiness](https://www.luogu.com.cn/problem/P1646)**
一个班级是$$n \times m$$矩阵，前后左右视为相邻，并视为好朋友
每个同学对文科和理科有一个喜好度，如果一对好朋友能够同时选择文科或者理科，又会增加一些喜好度
要求喜好度最大

实际上就是$$n \times m$$的矩阵，每个人可以选`A`或者选`B`，选`A`有一些收益，选`B`也有一些收益
如果一对朋友同时选`A`或者同时选`B`，又会有额外收益
使得收益最大

![](/media/content_img/mincut03.png)
![](/media/content_img/mincut04.png)

对于选理科的情况，也是类似操作，只不过是建一个辅助点，向`t`连边，流量上限是都选理科的额外代价

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

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

maxflow<i64> g(N+5);
    int idx = 2;
    vector<vector<int> > id(n+1, vector<int>(m+1, 0));

i64 ans = 0;

for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            id[i][j] = ++idx;
        }
    }

for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            i64 x;
            cin >> x;
            ans += x;
            
            g.addEdge(s, id[i][j], x);
        }
    }

for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            i64 x;
            cin >> x;
            
            ans += x;
            g.addEdge(id[i][j], t, x);
        }
    }

for (int i = 1; i <= n-1; i++) {
        for (int j = 1; j <= m; j++) {
            i64 x;
            cin >> x;

ans += x;
            auto now = ++idx;
            g.addEdge(s, now, x);
            g.addEdge(now, id[i][j], inf<i64>);
            g.addEdge(now, id[i+1][j], inf<i64>);
        }
    }

for (int i = 1; i <= n-1; i++) {
        for (int j = 1; j <= m; j++) {
            i64 x;
            cin >> x;

ans += x;
            auto now = ++idx;
            g.addEdge(now, t, x);
            g.addEdge(id[i][j], now, inf<i64>);
            g.addEdge(id[i+1][j], now, inf<i64>);
        }
    }

for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m-1; j++) {
            i64 x;
            cin >> x;

ans += x;
            auto now = ++idx;
            g.addEdge(s, now, x);
            g.addEdge(now, id[i][j], inf<i64>);
            g.addEdge(now, id[i][j+1], inf<i64>);
        }
    }

for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m-1; j++) {
            i64 x;
            cin >> x;

ans += x;
            auto now = ++idx;
            g.addEdge(now, t, x);
            g.addEdge(id[i][j], now, inf<i64>);
            g.addEdge(id[i][j+1], now, inf<i64>);
        }
    }
    
    i64 res = ans - g.dinic(s, t);
    cout << res << "\n";
}
```
## Educational Codeforces Round 171 E
**[E. Best Subsequence](https://codeforces.com/contest/2026/problem/E)**
给定长度为`n`的序列`a`，定义序列的分数
是数组的长度减去所有按位`or`的结果中`1`的个数
比如`[1, 0, 1, 2]`，按位`or`的结果是`3`，`3`有`2`个`1`，因此数组的值是`4 - 2 = 2`
现在要求计算给定序列的某个子序列可能获得的最大值

**算法分析**
```bash
选了几个数 - 几个数位为 1
= len - [bit = 1]
```
不难发现，在这个问题中，你选了$$a_i$$，意味着$$a_i$$**所有为`1`的数位都要选**
那么很容易想到**最大权闭合子图**

这样做对不对呢？考虑贡献
选了`a[i]`，就意味着对答案有`+1`的贡献，同时$$a_i$$中所有为`-1`的数位对答案有`-1`的贡献
这恰好是符合**最大权闭合子图模型的**

两排点，左边一排是`a[1...n]`，右边一排是`j = [0...60)`表示数位
考虑$$(s, a_i, 1), (n + j, t, 1)$$，然后$$(a_i, n+j, +\infty)$$连边，最后答案就是`n - dinic(s, t)`

看完文章有啥想法

算法小站

wiki 主题

图论

最小割及应用

目录