wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

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

图论

图的连通性

有向图的强连通分量

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

流和匹配

最大流

最大流的一些应用

[[ item.c ]]

最大流的应用

## 最大流问题
### 二分图匹配问题
源点向每个点连$$1$$的流量，每个点向汇点连$$1$$的流量
二分图原来就有的边，连$$+\infty$$的流量
在图上跑一遍最大流，就得到了一个最大匹配

证明，因为每个点通往源，汇的流量上限都是$$1$$，所以每个点最多只会被用到一次

**[网络流 24 题 试题库](https://ac.nowcoder.com/acm/problem/213904)**
给定$$n$$道试题，每一道试题标明了所属的类别，同一道题可能属于多个类别属性
现在需要抽出$$m$$题组成试卷，并且要求试卷包含指定类型的试题，计算方案

**算法分析**
1）考虑到$$n$$道题，不一定每一题都要出，但是一道题有多个 tag，怎么来描述这件事情呢？
可以看作是**匹配**，比如一道题有 3 个知识点，可以看作`(tag1, tag2, tag3) <--> (item1)`相匹配

2）考虑限制，比如 tag1 要出 3 道题，怎么办呢？
不妨设包含 tag1 的题目有`(item1, item2, ....., itemk)`，要在`item[1...k]`中选 3 题
可以考虑对于每个$$(tag_1, item_i)$$连一条流量上限为$$1$$的边
同时$$s \to tag_1$$连一条流量上限为$$3$$的边

3）注意到一道题目出一次，你不能出重复的题目，所以对每个$$item_i \to t$$连流量上限为$$1$$的边

4）最后还有一个问题，怎么判断是否合法？只需要看`dinic() == (S 流出去的所有流量)`，即判断满流即可
`S 流出去的所有流量`，在输入的时候即可计算出来
那方案数呢？实际上，对于$$(u, v), u \in \text{tag}, v \in \text{item}$$，如果$$flow(u, v) = 1$$
它实际上真的流了$$1$$的流量，就可以认为是`u 这个知识点，选择出题目 v`

> 输出的时候，注意一下，右边那一排关于 item 的点，编号是`k + j`，对应到实际的题目，应该是`v - k`

### Dicing
**[POI 2005 Dicing](https://ac.nowcoder.com/acm/problem/211215)**
**问题描述**
很多局游戏，知道每一局游戏对弈的是哪两个选手。每局游戏有一个赢家，现在要你找到能够赢最多的那个人
并且决策那个人**最少**会赢多少场
就是让赢得多的人，赢得场次尽可能少

#### 算法分析
> 这又是一个最大值最小的问题，可以考虑二分答案，赢得最多的那个人赢了$$x$$场，最小化这个$$x$$

判断的时候，考虑是不是所有玩家赢的场数都$$\leqslant x$$

> 怎么来进一步分析呢？

这实际上也是一个分配问题，注意到一局游戏只有一个赢家，也就是说**要为每一个游戏分配一个玩家**
有什么限制呢？那就是一个游戏只能被选一次（分配完了之后，就不会再选这个游戏了）
可以考虑从`s -> 游戏`连一条流量上限是`1`的边

那么玩家呢？一个玩家可能会赢好几场，二分$$x$$之后，每个玩家赢的场数$$\leqslant x$$
也就是说，每个玩家可以被**经过**的次数，上限就是$$x$$
此时`玩家 -> t`连一条流量上限是`x`的边即可

一局游戏 2 个玩家，游戏`u->v1, u->v2`分别连流量上限是`1`的边

什么时候有解呢？
那就是为每一个游戏，都找到一个**匹配玩家**，假设有$$m$$局游戏，那么必须满流，`dinic() == m`有解

### 卡点的流量
**[网络流 24 题 最长递增子序列问题](https://ac.nowcoder.com/acm/problem/213820)**
给定一个序列`x[1...n]`
1）计算其不下降子序列（非严格 LIS）的长度`s`
2）计算从给定的序列中最多能取出多少个长度为`s`的不下降子序列，要求每个数只能被选一次
3）如果允许在序列中多次取$$x_1, x_n$$，问从给定的序列中最多取多少个长度为`s`的不下降子序列

#### 算法分析
这里题目中，第二问要求取 LIS，每个数只能被选一次

>  求 LIS 很容易，难点在于，怎么根据这个 LIS 信息来建模？难点是怎么处理**一个数只能被选一次**这个问题

流实际上是一条路径，从$$s \to t$$的最大流，好像也能被看作是一种方案？
比如上升子序列$$a_i \leqslant a_j$$，那么能不能$$(i, j)$$连流量上限是$$1$$的边呢？

这样好像是可以做的，第一问用 dp 求解，如果$$dp_v = dp_u + 1$$，并且$$a_u \leqslant a_v$$
那么我们考虑$$u \to v$$连流量是$$1$$的边
注意到对于$$u$$而言，满足$$dp_u + 1$$的`v`可能有很多个，比如`dp(v1), dp(v2), dp(v3), ...`
都依次连边，这样就满足了**最长上升**这一限制

> 那么多种方案，并且**每个数只能被选一次**，怎么满足呢？

如果按照上述方法去构造，从`dp = 1`的点跑到`dp = n`的点，只能得到一种方案
解决方法是，$$s$$向每一个`dp = 1`的点连$$+\infty$$的边，同时所有`dp = n`的点向$$t$$连$$+\infty$$的边
这样跑最大流可以跑出多种方案

那么这样做又有一个问题
比如`5`这个点，有**多条出边**，那么在`5`这个点多路增广的时候，`5`会被选多次，怎么保证**只被选一次呢**？

> 一个点只选一次，考虑拆点，卡点的流量

之前说的，满足$$a_i \leqslant a_j, dp_j = dp_i + 1$$的$$i \to j$$，考虑拆点
预处理拆点，对于每个点$$i$$，在$$i \to i'$$连一条流量为$$1$$的边

建图的时候，根据 dp 值的关系，对$$(i, j)$$连边，拆成$$(i' \to j)$$连一条流量上限为$$1$$的边
（拆点的实现很简单，比如$$i' = i+n$$，就用来对应拆出来的点）

这样跑一遍$$s \to t$$的最大流就是答案

> 那么第三个条件$$x_1, x_n$$可以被选多次怎么办呢？

拆点的时候，$$(1, 1'), (n, n')$$连流量上限为$$+\infty$$的边即可

> 注意点，`dp(j) = dp(i) + 1`和`a[i] <= a[j]`两个条件要同时限制住

否则，比如说
```bash
5 11 16
5 8 9
都构成长度为 3 的 LIS，注意到 9 这个点的长度 dp(9) = 3 = dp(11) + 1
实际上 11，9 并不构成 LIS
```

另外还需特判，如果 LIS 的长度本身就是`1`，那么$$1, n$$是不能拆成$$(1, 1', +\infty), (n, n', +\infty)$$的

#### 算法实现
```bash
typedef pair<int, int> PII;
 
void solve() {
    int n;
    cin >> n;
    vector<int> a(n+1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];
 
    // dp 
    vector<int> dp(n+1, 0);
    for (int i = 1; i <= n; i++) {
        dp[i] = 1;
        for (int j = 1; j < i; j++) if (a[j] <= a[i]) {
            chmax(dp[i], dp[j] + 1);
        }
    }
 
    int res = *max_element(dp.begin(), dp.end());
    cout << res << "\n";
    int s = 2 * n + 1, t = 2 * n + 2;
     
    // part 02
    {   
        if (n == 1) {
            cout << "1\n";
            return;
        }
        maxflow<int> g(2*n + 15);
        for (int i = 1; i <= n; i++) g.addEdge(i, i + n, 1);
        for (int i = 1; i <= n; i++) {
            if (dp[i] == 1) g.addEdge(s, i, n);
            if (dp[i] == res) g.addEdge(i + n, t, n);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                if (dp[i] == dp[j] + 1 && a[j] <= a[i]) g.addEdge(j+n, i, 1);
            }
        }
 
        auto flow = g.dinic(s, t);
        cout << flow << "\n";
    }
    // part 03
    {
        if (n == 1) {
            cout << "1\n";
            return;
        } 
        maxflow<int> g(2*n + 15);
        for (int i = 1; i <= n; i++) {
             
            if ((i != 1 && i != n) || res == 1) g.addEdge(i, i + n, 1);
            else g.addEdge(i, i + n, n);
        }
        for (int i = 1; i <= n; i++) {
            if (dp[i] == 1) g.addEdge(s, i, n);
            if (dp[i] == res) g.addEdge(i + n, t, n);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                if (dp[i] == dp[j] + 1 && a[j] <= a[i]) g.addEdge(j+n, i, 1);
            }
        }
 
        auto flow = g.dinic(s, t);
        cout << flow << "\n";
    }
}
```

看完文章有啥想法

算法小站

wiki 主题

图论

最大流的应用

目录