二分图 学习笔记

模板及讲解
二分图相关定义
二分图:对于某无向图 ,若它的顶点可以划分为两个互不相交的子集 ,且每条边的两端点分别属于两子集 ,则称该图为二分图
(二分图)匹配:选择一个 边集 ,使得任意边 不存在重复的顶点 ,称该边集为该(二分)图的一个 匹配 。
极大匹配:对于一个匹配,若无法在原图中找到任意边加入匹配,则称该匹配为一个极大匹配。
最大匹配:一个图所有匹配中,所含匹配边数最多的匹配,称为这个图的最大匹配
交替路:从一个未匹配点出发,依次经过非匹配边、匹配边、非匹配边 …形成的路径叫 交替路
增广路:对于一条路径,从一个未匹配点出发,走交替路,终止于另一个未匹配点 ,则这条交替路称为增广路

增广路的性质:
1、具有奇数条边
2、起点和终点均为未配对点
3、整条路径上奇数边均不在原匹配中,偶数边均在原匹配中

二分图的最大匹配
普通网络流做法$O(n \sqrt{m})$:
dinic虽是$O(n^2m)$的,但是做二分图被证明了复杂度为$O(n \sqrt{m})$,详情做法看最大流最小割 算法笔记

匈牙利算法做法$O(nm)$:
算法思路大致为(具体实现看相关代码):先枚举每个左边点DFS找右边点匹配,如果当期右边点没有被匹配,就匹配;如果被匹配了,就继续DFS这个右边点匹配的左边点找另外的点匹配,如果找得到,就完成匹配;找不到,就不能够匹配了
比较”专业”的说法:
找到一未配对点$ u$,从 $u $为端点的边中任选一条尝试配对(令其另一端点为$ v$),若此时$ v$ 未配对,则配对成功,答案更新。若点$ v$ 已经被配对,就尝试从$ v $出发“扩展”该交替路,执行递归操作,尝试找到一条增广路,若成功,对该增广路取反,即回溯更新配对关系。若失败,则尝试换一条以 $u$ 为端点的边重复操作,直至$ u$ 配对成功或全部尝试过为止。
对所有剩下的未配对点进行操作,直至尝试完毕所有点,找不到增广路为止,此时找到原图最大匹配~

二分图的最小点覆盖
定义:假如选了一个点就相当于覆盖了以它为端点的所有边。最小顶点覆盖就是选择最少的点来覆盖所有的边。
解法:二分图最大匹配 $=$ 二分图最小点覆盖(König 定理)
因为如果该图还会有边没覆盖到,二分图的当前匹配就不是最大匹配。因为二分图匹配必须有一条边的两端都能让出位置才能匹配。
二分图的最大独立集
定义:选出一些顶点使得这些顶点两两不相邻,则这些点构成的集合称为独立集。找出一个包含顶点数最多的独立集称为最大独立集。
解法:最大独立集 $=$ 所有顶点数 $-$ 最小顶点覆盖(匈牙利算法:最大独立集 $=$ 所有顶点数 $-$最小顶点覆盖$/2$,因为匈牙利算法是针对有向边的而最大独立集的边是无向边)
这个比较显然, 最小顶点覆盖把所有边的一个顶点都算上了,其他点不会再有相邻的
二分图的最大团
定义:对于一般图来说,团是一个顶点集合,且由该顶点集合诱导的子图是一个完全图,简单说,就是选出一些顶点,这些顶点两两之间都有边。最大团就是使得选出的这个顶点集合最大。对于二分图来说,我们默认为左边的所有点之间都有边,右边的所有顶点之间都有边。那么,实际上,我们是要在左边找到一个顶点子集X,在右边找到一个顶点子集Y,使得X中每个顶点和Y中每个顶点之间都有边。
解法:二分图的最大团 $=$ 补图的最大独立集
补图的定义:对于二分图中左边一点$x$和右边一点$y$,若$x$和$y$之间有边,那么在补图中没有,否则有。
因为最大独立集是两两不相邻,所以最大独立集的补图两两相邻。
DAG的最小不相交路径覆盖
定义:在一个有向图中,找出最少的路径,使得这些路径经过了所有的点,且这些路径不可以相交。不相交即任何一个顶点有且只有一条路径与之关联。
解法:把一个点$A$拆成$A_1, A_2$,如果$A->B$,那么$A_1->B_2$。然后对新图进行二分图最大匹配,答案为 原图的节点数 $-$ 新图的二分图最大匹配
因为先假设图中的点都是独立的一条路径,而二分图最大匹配的过程就是把这些路径连起来。
DAG的最小可相交路径覆盖
定义:在一个有向图中,找出最少的路径,使得这些路径经过了所有的点,这些路径可以相交。
解法:算出图的连通性$G$,把一个点$A$拆成$A_1, A_2$,如果$G(A, B) = 1$,那么$A_1->B_2$,转化为DAG的最小不相交路径覆盖
(以上部分内容转自此处此处)

行列匹配法(模型)
有很多箭,每根箭可以杀死一行或者一列的敌人,我们要杀死所有的敌人至要用到几根箭?
每个敌人的坐标$(x, y)$建图,由左边$x$连向右边$y$,然后求最小顶点覆盖即可。
因为这个图中的一条边$(x, y)$相当于原来的$(x, y)$处的敌人,所以覆盖所有边即可以全部杀死。

常见题型:
1、求二分图的最大匹配
Q: 给定一个二分图,求它的最大匹配
解: 见解析
例题:Bzoj 1191
2、求二分图最小点覆盖
Q: 给定一个二分图,求它的最小点覆盖
解: 见解析
例题:caioj 1125
3、求二分图的最大独立集
Q: 给定一个二分图,求它的最大独立集
解: 见解析
例题:
4、二分图的最大团
Q: 给定一个二分图,求它的最大团
解: 见解析
例题:
5、DAG的最小不相交路径覆盖(拆点)
Q: 给定一个DAG图,求它最小不相交路径覆盖
解: 见解析
例题:Bzoj 2150
6、DAG的最小可相交路径覆盖(拆点)
Q: 给定一个DAG图,求它最小可相交路径覆盖
解: 见解析
例题:
7、行列匹配法(模型, 以上题型为基础题型)
Q: 有很多箭,每根箭可以杀死一行或者一列的敌人,我们要杀死所有的敌人至要用到几根箭?
解: 见解析
例题: Bzoj 1059, caioj 1126

二分图匈牙利算法(Bzoj 1191):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 1000 + 5;
int cnt, n, m, lk[MAXN], vis[MAXN];
//lk[u]=i: 右边的u点被左边的i点匹配
//vis[u]=i: 第i轮左边的u点被尝试更改(不设为bool是因为这样免去每次重置数组)
vector<int> G[MAXN];
//记录左边点->右边点的边
bool hungary(int u) {
for (int i = 0; i < G[u].size(); i++) {//枚举每个右边的点匹配
int v = G[u][i];
if (vis[v] != cnt) {//尝试修改过的节点就不需要遍历了
vis[v] = cnt;
if (!lk[v] || hungary(lk[v])) {
//如果枚举的右边点没被匹配,就可以直接匹配。如果已经被匹配了,那么就让之前
//匹配这个右边点的左边点去匹配另一个点,让这个点去匹配这个右边点。
//这里运用了||的性质,||左边如果为true就不在执行||右边的表达式
lk[v] = u;
return true;//成功匹配
}
}
}
return false;
}
void clean() {
for (int i=0;i<=max(n, m);i++) vis[i] = lk[i] = 0, G[i].clear();
}
void solve() {
clean();
for (int a, b, i = 1; i <= m; i++) {//可以把u, v压行qwq
scanf("%d%d", &a, &b);
G[i].push_back(a), G[i].push_back(b);
}
int ans = 0;
for (int i = 1; i <= m; i++) {
if (hungary(cnt = i)) ans++; else break;//枚举每个左边的点匹配,如果一道题不能做出来就要break,因为不能进入下一关了,而正常二分图最大匹配这样写是不行的
}
printf("%d\n", ans);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
scanf("%d%d", &n, &m), solve();
return 0;
}

------ 本文结束 ------