二分图最大匹配

二分图最大匹配

思想

大牛博客

另一个大牛博客

本节内容根据上述资料改编而来。

核心思想: 调整思想

假设我们现在身处相亲大会,每个女孩都有几个心仪的男孩,每个男孩也都有几个心仪的女孩。 (如果这里出现了同性恋,那么就不是二分图了…)

那么我们最多可以撮合几对呢? 这就是二分图最大匹配问题。

如图,每一条红线表示互相有好感。(单相思是不可能的,谁愿意将就呢对吧)

它的最大匹配是

清楚了问题,接下来就要解决如何求的问题。

这个算法的思想核心就是 : 男生都有一颗(不过分的)舍己为人的心。

比如现在我先选择了徐佳莹,接下来下一个boy也选择了徐佳莹。这时候即使我再怎么喜欢徐佳莹,因为我舍己为人的心,我也要把徐佳莹让出来。然后我重新选择了张碧晨,但是我发现在我之前已经有boy选了张碧晨。这时候同样的,他也会忍痛割爱把碧晨让给我,然后他再去选择其它女生。

当然了,如果我只喜欢徐佳莹,而对其它女生没有兴趣。那么当下个boy选择徐佳莹的时候我是不会拱手送人的。这就是所谓的不过分,自己都没有对象了,就不要管别人了。

具体的实现使用递归的方法: 如果我选了徐佳莹,但是徐佳莹被林俊杰选了,那么继续去递归林俊杰,看看他是否能选别人。如果不行的话,我再换一个选。

接下来给出了两种实现方式,邻接表和邻接矩阵。

这里有个小小的说明

为什么邻接矩阵用girl而邻接表里用linker?

因为邻接表里linker[u] == v,说明u和v匹配,那么同样的linker[v] == u. 这样可以快速查询某人的配偶是谁。

模板

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
// 邻接矩阵
// 复杂度 O(nx * ny)
// 点的编号 boy: 0 ~ n-1. girl: 0 ~ m-1. 只建单向边
bool vis[maxn];
int G[maxn][maxn],girl[maxn];
int n; // boy 数量
int m; // girl 数量

void addedge(int u,int v){
G[u][v] = 1; // boy -> girl
}

bool find(int x) {
for (int i = 0; i < m; i++) {
if (G[x][i] && !vis[i]) {
vis[i] = true;
if (girl[i] == -1 || find(girl[i])) {
girl[i] = x;
return true;
}
}
}
return false;
}
int hungary() {
int ret = 0;
memset(girl, -1, sizeof(girl));
for (int i = 0; i < n; i++) {
memset(vis, 0, sizeof(vis));
if (find(i)) ret++;
}
return ret;
}
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
// 邻接表
// 复杂度 O(V * E)
// 注意点的编号。 boy : 0 ~ n-1. girl: n ~ n+m-1.
bool vis[maxn];
vector<int> G[maxn];
int linker[maxn];

void init(int n) { // 这里n为总人数
for (int i = 0; i <= n; i++) G[i].clear();
}
void addedge(int u, int v) {
G[u].push_back(v);
G[v].push_back(u);
}

bool find(int u) {
vis[u] = true;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
int vv = linker[v];
if (vv < 0 || !vis[vv] && find(vv)) {
linker[v] = u;
linker[u] = v;
return true;
}
}
return false;
}

int hungary(int n) { // n 为boy的数量(如果已知boy数量) 或 总人数
int ret = 0;
memset(linker, -1, sizeof(linker));
for (int i = 0; i < n; i++) {
if (linker[i] < 0) {
memset(vis, 0, sizeof(vis));
if (find(i)) ret++;
}
}
return ret;
}
Thank you for your support!