Chgtaxihe's blog

二分图匹配学习笔记

# 二分图匹配

给定一个二分图，其左部点的个数为 nn，右部点的个数为 mm，边数为 ee，求其最大匹配的边数。

# 名词解析

  • 匹配：一个图的边的子集，其中任意两条边都没有公共顶点
  • 最大匹配：一个图的所有匹配中，所含匹配边数最多的匹配
  • 完美匹配/完全匹配：如果某个匹配中，所有顶点都是匹配点，则该匹配为完美匹配

# 性质/结论

# 匈牙利算法

每找到一条增广路经（未匹配-匹配-未匹配-....-未匹配），都可以使得匹配对数+1

匈牙利算法所做的便是不断寻找增广路经

时间复杂度O(VE)O(VE)

以下代码对应洛谷P3386

左部点从 11 至 nn 编号，右部点从 11 至 mm 编号，求最大匹配。

# DFS写法

比较好理解

#include <bits/stdc++.h>
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

const int max_left = 500 + 100;
const int max_right = 500 + 100;
const int maxe = 5e4 + 1000;

int head[max_left], nxt[maxe], dest[maxe];
int matching[max_right], vis[max_left];

bool dfs(int u, int time_tag){
    if(vis[u] == time_tag) return false;
    vis[u] = time_tag;
    for(int e=head[u]; e; e=nxt[e]){
        if(matching[dest[e]] == 0 || dfs(matching[dest[e]], time_tag)){
            matching[dest[e]] = u;
            return true;
        }
    }
    return false;
}

void solve(){
    int left_cnt, right_cnt, edge_cnt, ans = 0;
    cin >> left_cnt >> right_cnt >> edge_cnt;

    for(int i=1, u, v; i<=edge_cnt; i++){
        cin >> u >> v;
        nxt[i] = head[u], dest[i] = v;
        head[u] = i;
    }

    for(int i=1; i<=left_cnt; i++){
        if(dfs(i, i)) ans++;
    }
    cout << ans << '\n';
}

signed main(){
    Android;
    solve();
}
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

# BFS写法

在dfs的基础上进行修改，复杂度更优(?)

#include <bits/stdc++.h>
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

const int max_left = 500 + 100;
const int max_right = 500 + 100;
const int maxe = 5e4 + 1000;

int head[max_left], nxt[maxe], dest[maxe];
int matching_x[max_left], matching_y[max_right], vis[max_left];

int que[max_left], prev_n[max_left];
int bfs(int lcnt){

    int u, v, tmp, e, qs, qe, cnt = 0;
    bool found;

    for(int i=1; i<=lcnt; i++){
        qs = qe = 0;
        found = false;
        vis[i] = que[qe++] = i;
        prev_n[i] = -1;

        while(qs < qe && !found){
            u = que[qs++];
            for(e = head[u]; e; e = nxt[e]){
                v = dest[e], tmp = matching_y[v];
                if(tmp != 0 && vis[tmp] == i) continue;
                if(tmp != 0){
                    que[qe++] = tmp;
                    prev_n[tmp] = u;
                    vis[tmp] = i; // time tag
                }else{
                    found = true;
                    while(u != -1){
                        tmp = matching_x[u];
                        matching_x[u] = v;
                        matching_y[v] = u;
                        u = prev_n[u], v = tmp;
                    }
                    break;
                }
            }
        }

        if(found) cnt++;
    }
    return cnt;
}

void solve(){
    int left_cnt, right_cnt, edge_cnt;
    cin >> left_cnt >> right_cnt >> edge_cnt;

    for(int i=1, u, v; i<=edge_cnt; i++){
        cin >> u >> v;
        nxt[i] = head[u], dest[i] = v;
        head[u] = i;
    }
    cout << bfs(left_cnt) << '\n';
}

signed main(){
    Android;
    solve();
}
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66

# 带权二分图最优匹配(Kuhn-Munkres)

KM算法在稠密图上比费用流更优秀一些

# 算法步骤

  1. 初始化顶标
  2. 通过匈牙利算法寻找完备匹配
  3. 若找不到，修改标杆来增加一些边，重复步骤2

# 算法部分解析

在任意时候，都有A[i]+B[j]≥wijA[i]+B[j]\ge w_{ij}，其中Au,BvA_u,B_v分别为点u,vu,v的顶标

在运算的过程中的子图，边(u,v)(u,v)存在当且仅当Au+Bv=wuvA_u+B_v=w_{uv}

# 算法模板

对应题目：洛谷P6577

给定一张二分图，左右部均有 nn 个点，共有 mm 条带权边, 且保证有完美匹配。

求一种完美匹配的方案，使得最终匹配边的边权之和最大。

# 朴素DFS版(4AC, 6TLE)

用于理解KM算法的模板，该模板在优化（slack）后可以在随机数据上做到O(n3)O(n^3)（即伪O(n3)O(n^3)）

#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

struct Kuhn_Munkres{ // 复杂度O(n^4)，必须保证存在完备匹配
    const static int max_node = 500 + 100;
    const static ll inf = 0x3f3f3f3f3f3f3f3f;
    int n, match_y[max_node];
    ll G[max_node][max_node];
    ll cx[max_node], cy[max_node]; // 顶标
    bool vis_x[max_node], vis_y[max_node];

	void init(int node_cnt){
        n = node_cnt;
        for(int i=0; i<=n; i++){ // 添加虚边
            cx[i] = cy[i] = match_y[i] = 0;
            for(int j=0; j<=n; j++) G[i][j] = -inf;
        }
    }

    bool dfs(int u, ll & delta){ // 匈牙利算法
        vis_x[u] = true;
        for(int v=1; v<=n; v++){
            if(vis_y[v]) continue;
            if(cx[u] + cy[v] == G[u][v]){
                vis_y[v] = true;
                if(match_y[v] == 0 || dfs(match_y[v], delta)) {
                    match_y[v] = u;
                    return true;
                }
            }else{
                delta = min(delta, cx[u] + cy[v] - G[u][v]);
            }
        }
        return false;
    }

    ll km(){
        memset(cx, 0x8f, sizeof cx);
        for(int i=1; i<=n; i++){ // 初始化顶标
            for(int j=1; j<=n; j++) cx[i] = max(cx[i], G[i][j]);
        }

        for(int u=1; u<=n; u++){
            while(true){ // 直到找到增广路才离开循环
                memset(vis_x, 0, sizeof vis_x);
                memset(vis_y, 0, sizeof vis_y);
                ll delta = inf;
                if(dfs(u, delta)) break;
                for(int i=1; i<=n; i++){
                    if(vis_x[i]) cx[i] -= delta;
                    if(vis_y[i]) cy[i] += delta;
                }
            }
        }

        ll ans = 0;
        for(int i=1; i<=n; i++) ans += G[match_y[i]][i];
        return ans;
    }
    
}km;

void solve(){
    int n, m;
    cin >> n >> m;
    km.init(n);
    for(int i=0, u, v, w; i<m; i++){
        cin >> u >> v >> w;
        km.G[u][v] = w;
    }
    cout << km.km() << '\n';
    for(int i=1; i<=n; i++) cout << km.match_y[i] << (i==n?'\n':' ');
}

signed main(){
    Android;
    solve();
}
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

# DFS优化(5AC,5TLE)

网上搜了半天也没找到“slack“优化的原理，自己琢磨了一下，有了一个猜想

具体原理是：如果拓展子图时，添加了一条边(u,v)(u,v)，若仍没有找到增广路，那么下一次拓展子图时，不需要添加任何以vv为右部点的边。

以下代码与网上的slack优化相比，不同点在于if(vis_y[i]) cy[i] += d; else slack[i]-=d;，个人认为当!vis_y[i]时，slack[i]slack[i]减少与否不影响正确性。？？？

该模板AC题目:HDU 2255

struct Kuhn_Munkres{
    const static int max_node = 500 + 10;
    const static ll inf = 0x3f3f3f3f3f3f3f3f;
    int n, match_y[max_node];
    ll G[max_node][max_node], delta[max_node];
    ll cx[max_node], cy[max_node];
    bool vis_x[max_node], vis_y[max_node];

    void init(int node_cnt){} // 省略

    bool dfs(int u){
        vis_x[u] = true;
        for(int v=1; v<=n; v++){
            if(vis_y[v]) continue;
            if(cx[u] + cy[v] == G[u][v]){
                vis_y[v] = true;
                if(match_y[v] == 0 || dfs(match_y[v])) {
                    match_y[v] = u;
                    return true;
                }
            }else{
                delta[v] = min(delta[v], cx[u] + cy[v] - G[u][v]);
            }
        }
        return false;
    }

    ll km(){
        memset(cx, 0x8f, sizeof cx);
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++) cx[i] = max(cx[i], G[i][j]);
        }

        for(int u=1; u<=n; u++){
            memset(delta, 0x3f, sizeof delta);

            while(true){
                memset(vis_x, 0, sizeof vis_x);
                memset(vis_y, 0, sizeof vis_y);
                ll d = inf;
                if(dfs(u)) break;
                 // 已经被松弛过的点,一定会被vis
                for(int i=1; i<=n; i++){
                    if(!vis_y[i]) d = min(d, delta[i]);
                }
                for(int i=1; i<=n; i++){
                    if(vis_x[i]) cx[i] -= d;
                    if(vis_y[i]) cy[i] += d;
                }
            }
        }

        ll ans = 0;
        for(int i=1; i<=n; i++) ans += G[match_y[i]][i];
        return ans;
    }
    
}km;
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
53
54
55
56
57
58

# BFS写法

每次扩大子图最少会添加11条边，可能会扩大O(n2)O(n^2)次，每次扩大后都要重新DFS一遍（O(n2)O(n^2)），复杂度接近O(n4)O(n^4)

考虑减少扩大子图后dfsdfs的复杂度，我们需要维护每一个右部点可能"来自"于哪一个左部点，又因为每个右部点在扩大子图时最多只会被访问1遍，因而有如下代码

# BFS 迭代写法 (AC)

详细过程见代码内注释

#include <bits/stdc++.h>
#define ll long long
using namespace std;

struct Kuhn_Munkres{ // 复杂度O(n^3)，必须保证存在完备匹配
    const static int max_node = 500 + 10;
    const static ll inf = 0x3f3f3f3f3f3f3f3f;
    int match_y[max_node], pre[max_node], lcnt, rcnt;
    ll G[max_node][max_node], slack[max_node];
    ll cx[max_node], cy[max_node]; // 顶标
    bool vis_y[max_node];

    void init(int l, int r){
        lcnt = l, rcnt = r;
        for(int i=0; i<=lcnt; i++) cx[i] = 0;
        for(int i=0; i<=rcnt; i++) cy[i] = match_y[i] = 0;
        for(int i=0; i<=l; i++){ // 添加虚边
            for(int j=0; j<=r; j++) G[i][j] = -inf;
        }
    }

    void bfs(int u){
        int x, y = 0, next_y;
        ll min_delta;
        for(int i=0; i<=rcnt; i++) pre[i] = 0, slack[i] = inf;
        match_y[y] = u;
        
        do{ // 包括初始化顶标、寻找增广路都在下面的do while中完成
            x = match_y[y], min_delta = inf, vis_y[y] = true;
            for(int i=1; i<=rcnt; i++){
                if(vis_y[i]) continue;
                if(slack[i] > cx[x] + cy[i] - G[x][i]){
                    slack[i] = cx[x] + cy[i] - G[x][i];
                    pre[i] = y;
                    // pre中维护的不是i来自与哪一个左部点，而是维护这一条路径的上一个右部点
                    // 因为一个左部点可以对应多个右部点，而一个右部点只能对应一个左部点
                    // 上一个左部点可以通过match_y[pre[i]]得到
                }
                if(slack[i] < min_delta) next_y = i, min_delta = slack[i];
            }

            if(min_delta != 0){
                for(int i=0; i<=rcnt; i++){ // 从0开始(为了更新cx[u])
                    if(vis_y[i]) cx[match_y[i]] -= min_delta, cy[i] += min_delta;
                    else slack[i] -= min_delta; // 这里必须保持slack的正确性
                }
            }

            y = next_y;
        }while(match_y[y] != 0);
        // 沿途维护交错路信息
        while(y) match_y[y] = match_y[pre[y]], y = pre[y];
    }

    ll km(){
        for(int u=1; u<=lcnt; u++){
            for(int i=0; i<=rcnt; i++) vis_y[i] = false;
            bfs(u);
        }

        ll ans = 0;
        for(int i=1; i<=rcnt; i++) {
            if(match_y[i] != 0) ans += G[match_y[i]][i];
        }
        return ans;
    }
    
}km;

void solve(){
    int n, m;
    cin >> n >> m;
    km.init(n, n);
    for(int i=0, u, v, w; i<m; i++){
        cin >> u >> v >> w;
        km.G[u][v] = w;
    }
    cout << km.km() << '\n';
    for(int i=1; i<=n; i++) cout << km.match_y[i] << (i==n?'\n':' ');
}
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

# 注意事项

特别注意：左部点数必须小于等于右部点树，否则死循环（TLE）

当题目不一定存在完美匹配时，需要添加虚点、虚边。

例如：当判断是否有解时，可以添加一个虚点，并合理添加虚边，若该虚点被匹配，则无解（HDU 2426）。

# 参考链接

上次更新: 2021/02/24, 03:37:30
一般图最大匹配学习笔记
可撤销并查集学习笔记

← 可撤销并查集学习笔记→

最近更新
01
深入理解Java虚拟机
 03-04
02
DNS工作原理
 02-27
03
改用VuePress啦
 02-23
更多文章>
Theme by Vdoing | Copyright © 2019-2021