wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

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

图论

图的连通性

有向图的强连通分量

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

流和匹配

最大流

最大流的一些应用

最小割

费用流

带上下界的网络流

二分图匹配

二分图最大权匹配

图论杂项

最大团搜索算法

树上问题

kruskal重构树

kruskal重构树的一些问题

最短路

差分约束

[[ item.c ]]

二分图匹配

## Hopcroft-Karp定理
在`n`个点和`m`条边的二分图中，跑`dinic`算法，时间复杂度是$$O(m\sqrt{n})$$

> 证明如下

1）每一轮多路增广，复杂度是线性的$$O(n+m)$$
因为是二分图匹配，所以边权都是`1`，一旦找到一条增广路，从$$s \to t$$**一整条路径**都会被删掉
（对比普通的网络流，可能只会删掉一条边，然后回溯）

dinic 在二分图多路增广，如果到不了终点，回溯的时候榨干了流量，边也会被删掉
而如果能到终点呢？从$$s \to t$$一整条路径都删掉，而不是只删一条边，不存在回溯重新访问
由此**每条边最多会被访问一次**

2）只会做$$\sqrt{n}$$轮增广
![](/media/content_img/hopcroftKarp.png)

## Hall 定理
对于一个二分图，如果它有完备匹配（左边`n`个点，右边`n`个点，每个点都匹配了）
定义左边集合的**子集**为$$S$$，其邻居集合为$$N(S)$$（$$S$$中每个点的邻居的并）
```math
|N(S)| \geqslant |S|
```
这个条件是充要的，没有完备匹配，必然存在一个点集（子集），使得$$|N(S)| < |S|$$

> 正则图一定存在完备匹配

正则图每个点的度数都是`d`，左边每个点出去$$d$$条边，一共连出去$$d|S|$$条边
右边呢？右边每个点最多也只能接收$$d$$条边，所以右边需要的点数必须$$\geqslant |S|$$
才能够做到把`d`条边全部接收了

**拓展，**正则图能够划分成$$d$$组完备匹配

### TCO 2015 Revmatching
**[TCO 2015 1A Hard, Revmatching](http://oj.daimayuan.top/course/23/problem/1105)**
给定一个$$n$$个点的完全二分图，每条边有边权，求一个边权和最小的边集，使得删除该边集之后
不存在完备匹配，$$n \leqslant 20$$

**算法分析**
不存在完备匹配，只要能找到一个子集$$S$$，使得$$|N(S)| < |S|$$就可以了
枚举子集，删掉一些边使得邻居数量$$<$$子集数量

考虑$$S-N(S)$$，$$N(S)$$的大小要变成$$S - 1$$，要删掉$$del = N(S) - S + 1$$个点
怎么删？如果要删掉$$v$$，那么要把$$v \to |S|$$连的每一条边都删掉

先求出$$N(S)$$中每个点，将其删到和左边的点断开所需要的代价，然后从小到大选
枚举所有这样的集合，全局取一个最小值就可以了
```bash
void solve(int cas) {
    int n;
    cin >> n;

vector<vector<int> > a(n, vector<int>(n, 0));

for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) cin >> a[i][j];
    }

int ans = 1e9;
    for (int mask = 1; mask < (1 << n); mask++) {
        vector<int> wgt(n, 0);

for (int j = 0; j < n; j++) {
            for (int i = 0; i < n; i++) if (mask >> i & 1) {
                wgt[j] += a[i][j];
            }
        }

int del = n - popcnt(mask) + 1;
        sort(wgt.begin(), wgt.end());

int res = accumulate(wgt.begin(), wgt.begin()+del, 0);
        ans = min(ans, res);
    }

cout << ans << "\n";
}
```
### 2025 ICPC 网络赛
**[Jiaxun](https://qoj.ac/contest/2524/problem/14316)**
一共`3`个人，有`7`种类型的题目，`1, 2, 4`这三种类型的题目只能分别由队员`1, 2, 3`完成
而`3`可以由`1, 2`共同完成，`5`可以由`1, 3`共同完成，`6`可以由`2, 3`共同完成
而`7`可以由`1, 2, 3`共同完成

现在要最大化`min(每个队员做的题目)`，同时一个题目只能分配给一个队员做
这`7`种类型的题目数量分别是`F[1...7]`

**算法实现**
这是一个很标准的二分图匹配，**根据一个点能用几次**，这个点就向汇点连流量上限是多少的边
很显然可以二分答案`k`，左边`3`名同学，每名同学的解题数量上限就是$$k$$
那么从`(s, 学生)`连`k`的边

同时呢，对右边的点`i = [1...7]`，向汇点连流量上限是$$F_i$$的边

然后考虑队员`1`，他可以做`类型1, 3, 5, 7`的题，就向这些点连$$+\infty$$的边
其他的队员也是类似的，跑一遍最大流，看看是否满流，即$$flow \geqslant 3K$$是否满足

**特别说明**
```bash
maxflow<i64> g(N);
auto check = [&](int K) -> bool {
	g.init(N);
};

二分的时候，maxflow<i64> g(N) 要放在外面
之后建图的时候，在 check() 中去 addEdge
要不然会 TLE
```
> Hall 定理

考虑$$|S| \leqslant |N(S)|$$，假设说每个人能够解决的问题都$$\geqslant k$$
只看一个人的话
```math
\displaystyle
k \leqslant F_1 + F_3 + F_5 + F_7 \\
k \leqslant F_2 + F_3 + F_6 + F_7 \\
k \leqslant F_4 + F_5 + F_6 + F_7
```
如果看`2`个人的话，那么`(1, 2), (1, 3), (2, 3)`
```math
\displaystyle
2k \leqslant S - F_4 \\
2k \leqslant S - F_1 \\
2k \leqslant S - F_2
```
而看`3`个人的话，$$3k \leqslant S$$
对上述所有的$$k$$取一个最小值就是答案

## Dilworth 定理
针对**有向无环图 DAG**，最大反链 = 最小链覆盖

> 反链

找到一个集合$$S$$，使得$$S$$中的点**两两不可达**

> 链覆盖

找一些链来覆盖点，分为不可相交的，和可相交的
最大反链 = 最小链覆盖，链覆盖允许相交（可以有公共点）
![](/media/content_img/dilworth-01.png)

### 一般 DAG 求最小链覆盖
**[CTSC2008 祭祀](https://www.luogu.com.cn/problem/P4298)**
给定`n`个点`m`条边的 DAG，选择尽可能多的点，使得这些点两两不可达
实际上就是求最大反链的大小
输出一个`K`，表示最多能选择多少个这样的点

**算法分析**
对于一般的 DAG，求最大反链，实际上可以等价于求**最小链覆盖**，**用流来模拟路径**
这个题中，一个点可以被多次经过，构造如下流网络

1）拆点和内部边，将每个点$$u$$拆分成$$(in_u, out_u)$$，流量限制是$$[1, +\infty)$$
为了保证**最小链覆盖**，每个点都至少要被选一次，所以流量下界是`1`
因为允许链相交（即每个点可以被多次经过），所以流量上界是$$+\infty$$

2）原图的边，$$(u, v)$$对应$$out_u \to in_v$$，流量限制是$$[0, +\infty)$$

3）源$$s$$和汇$$t$$，从$$s \to$$`所有的点连边`，流量限制$$[0, +\infty)$$
所有的点向汇点$$t$$连边，流量限制是$$[0, +\infty)$$

在上述图中，跑**有源汇上下界最小流**（跑的时候还需要再建一个超级源和超级汇）
然后在残量网络上退流，`flow - 退流`就是答案
```bash
void solve(int cas) {
    int n, m;
    cin >> n >> m;

int N = 2 * n + 10;
    int s = N - 6;
    int t = s + 1, S = s + 2, T = s + 3;

auto in = [&](int u) { return 2 * u - 1; };
    auto out = [&](int u) { return 2 * u; };

maxflow<i64> g(N);

vector<i64> dx(N+5, 0);
    for (int x = 1; x <= n; x++) {
        auto X = in(x), Y = out(x);
        g.addEdge(X, Y, inf<i64> - 1);
        dx[X] -= 1, dx[Y] += 1;
    }

for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;

auto X = out(x), Y = in(y);
        g.addEdge(X, Y, inf<i64>);
    }

for (int x = 1; x <= n; x++) {
        g.addEdge(s, in(x), inf<i64>);
        g.addEdge(out(x), t, inf<i64>);
    }

for (int x = 1; x < N; x++) {
        if (dx[x] == 0) continue;
        if (dx[x] > 0) g.addEdge(S, x, dx[x]);
        else g.addEdge(x, T, llabs(dx[x]));
    }

g.addEdge(t, s, inf<i64>);

auto baseflow = g.dinic(S, T);
    auto flow = g.e.back().cap;

for (auto &e : g.e | views::drop(g.e.size() - 2)) {
        e.cap = 0;
    }

auto df = g.dinic(t, s);
    auto res = flow - df;

cout << res << "\n";
}
```
### 不可相交的链覆盖
可以单独考虑每个点，**尝试给每一个点找后继**
1）一开始所有的点都还没有找到后继，此时每个点都单独是一条链，总共有`n`条链
2）如果一个点找到了后继，那么就合并两个点，链的个数`-1`
3）如果最后`n - 1`个点都找到了后继，那么这些点就合并成一条链

**找后继也有限制**
每一个点至多一个后继，每个点至多一个前驱
**那么我们要找到尽量多的后继**，这容易让我们想到，将一个点拆成两个点
左边代表前驱，右边代表后继，然后求**二分图最大匹配**

这样的话，`最小链覆盖 = n - | 能满足成功找到后继的点的个数 |`

**能成功找到后继的点的个数**，又恰好是二分图最大匹配
对于`DAG`的边$$u \to v$$，考虑$$le_u \to ri_v$$连边
其中$$le_u$$表示左边一排点，$$ri_u$$表示右边一排点

组合意义是，$$le_u$$表示`u`被选为前驱，$$ri_v$$表示`v`被选为后继
而每个点被选为前驱/后继**最多一次**

**`最小链覆盖 = n - | 被选中的节点个数 |`**

### 可相交的链覆盖
![](/media/content_img/dilworth-02.png)

### CTSC2008 祭祀
**[CTSC2008 祭祀](https://www.luogu.com.cn/problem/P4298)**
给定`n`个点`m`条边的 DAG，选择尽可能多的点（被称为祭祀点），使得他们之间两两不可达
第一行输入最多能选多少个点
第二行构造方案，输出一个字符串，如果一个点被选中，那么`str[i] = 1`，否则是`0`
第三行，输出，选择最多的祭祀点的前提下，每个点能否设置称为祭祀点
输出字符串，如果可以，那么`str[i] = 1`，否则是`0`

> 第一问，预处理，得到闭包图，$$u \to v$$有向边存在，当且仅当$$u$$可达$$v$$

**在闭包图中**，对每个点$$u$$，拆成左右两排点，$$le_u, ri_u$$
对于有向边$$u \to v$$，考虑$$le_u \to ri_v$$连流量上限是`1`的边（表示`前驱 -> 后继`）
之后$$u$$就不能被选为前驱了，同时$$v$$也不能被选为后继

对应地，$$s \to le_u$$连`1`的边，$$ri_u \to t$$连`1`的边，`flow = dinic(s, t)`
最后`K = n - flow`就是答案

```bash
maxflow<int> g(N);
for (int x = 1; x <= n; x++) {
    g.addEdge(s, le(x), 1);
    g.addEdge(ri(x), t, 1);
}

for (int x = 1; x <= n; x++) {
    for (int y = 1; y <= n; y++) {
        if (!reach[x][y]) continue;
        g.addEdge(le(x), ri(y), 1);
    }
}

auto flow = g.dinic(s, t);
int K = n - flow;
```

> 第二问，怎么构造方案？什么样的点可以被选为**祭祀点？**

能被选为祭祀点的点，即求**最大独立集**，根据`Konig`定理
`最大独立集 + 最小点覆盖 = n`，可以考虑求**最小点覆盖**

而**最大匹配 = 最小点覆盖**，我们用`dinic`已经求出了最大匹配了，怎么根据这个最大匹配
构造最小点覆盖呢？
![](/media/content_img/dilworth-03.png)

根据上面的算法构造出最小点覆盖，然后取反，`右边 vis = false and 左边 vis = true`的点加入最大独立集

```bash
vector<int> res(n+1, 0), vis(N+5, 0);
auto bfs = [&]() -> void {
    queue<int> que;
    que.push(s), vis[s] = 1;

while (que.size()) {
        auto x = que.front(); que.pop();

for (auto i : g.g[x]) {
            auto [y, cap] = g.e[i];
            if (cap > 0 and !vis[y]) {
                que.push(y), vis[y] = true;
            }
        }
    }
};
bfs();

for (int i = 1; i <= n; i++) {
    if (vis[le(i)] and !vis[ri(i)]) res[i] = 1;
}
```

> 第三问，在选择最多祭祀点的前提下，单独考虑每个点能否成为祭祀点

要判断$$x$$能否作为祭祀点，考虑在图中删去$$x$$以及所有和$$x$$互相可达的点
剩下的点构成的子图跑最大匹配，如果剩下的图的最大反链恰好等于$$K-1$$，说明$$x$$可以选

```bash
// 考虑删除 x 以及 x 相关联的点，是否可行？
auto check = [&](int x) -> bool {
    vector<int> valid;
    for (int y = 1; y <= n; y++) {
        if (y != x and !reach[y][x] and !reach[x][y]) valid.emplace_back(y);
    }

maxflow<int> sub(N);
    for (int x = 1; x <= n; x++) {
        sub.addEdge(s, le(x), 1), sub.addEdge(ri(x), t, 1);
    }

for (int x : valid) for (int y : valid) {
        if (reach[x][y]) sub.addEdge(le(x), ri(y), 1);
    }

auto flow = sub.dinic(s, t);
    return valid.size() - flow == K - 1;
};
```

> 坑点

传递闭包，构造闭包图的时候，绝对不能有`reach(i, i) = true`
而题中给定的是个 DAG，也就是说，如果初始化`reach[...] = false`的话
`reach(i, i) |= (reach(i, k) & reach(k, i))`，其中`reach(i, k), reach(k, i)`**不可能同时为`true`**
所以`reach(i, i)`没有机会更新

## 一些特殊的问题
### ONTAK2010 Life of the Party
给定`n, m`的二分图，左边`n`个点右边`m`个点，求出哪些点一定在最大匹配中
也就是说，删除某个点，会导致最大匹配下降

**算法分析**
考虑**交错路**
![](/media/content_img/crossRoad-01.png)

```bash
// left
vector<int> vis(N+5, 0);
vector<vector<int> > e(N+5);

for (auto [x, y, cap, flow] : edges) {
	// 满流的浸润边，y --> x 走
	flow == 1 ? e[y].emplace_back(x) : e[x].emplace_back(y);
}
// 其余代码省略
for (auto x : candl) {
	if (!vis[x]) dfs(x);
}

```
### 稳定婚姻
**[稳定婚姻](https://www.luogu.com.cn/problem/P1407)**
给定`n`对夫妻，再给定`m`对关系，每一对关系表示**曾经相互喜欢过的情侣**（婚外情）
现在问每一对夫妻的婚姻是否安全

实际上就是给定`n`对匹配，另外还有`m`对匹配外的边
现在就是要考虑把每条边删了，是不是还有**完备匹配**（就是判断每条边是不是在完备匹配内）
这实际上是考虑**完备匹配的必须边**

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

看完文章有啥想法

算法小站

wiki 主题

图论

二分图匹配

目录