【洛谷-P2756】解题报告（二分图最大匹配）

原始题目

P2756 飞行员配对方案问题

题目大意

给定两个集合，存在一些连接两个集合的边表示配合，来自不同集合的一对元素构成一个配对，求最大的配对数量。

解题思路

集合内无边，所以构成二分图，求二分图的最大匹配。

解题代码

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<string, string> pss;

#define rep(i, a, n) for (int i = a; i < n; ++i)
#define per(i, a, n) for (int i = n - 1; i >= a; --i)
#define fi first
#define se second
#define mp make_pair
#define np next_permutation
#define pb push_back
#define INF 0x3f3f3f3f

const int maxn = 1e3 + 5;

vi e[maxn];
int n, m;
bitset<maxn> v;
int fa[maxn], ans;

int dfs(int x)
{
    rep(i, 0, e[x].size())
    {
        int y = e[x][i];
        if (v[y])
            continue;
        v[y] = 1;
        if (!fa[y] || dfs(fa[y])) {
            fa[y] = x;
            return 1;
        }
    }
    return 0;
}

void init()
{
    rep(i, 0, maxn) e[i].clear();
    memset(fa, 0, sizeof(fa));
    v.reset();
    ans = 0;
}

int main()
{
    ios::sync_with_stdio(false);
    while (cin >> m >> n) {
        init();
        int a, b;
        while (cin >> a >> b && a != -1) {
            e[a].pb(n + b);
            e[n + b].pb(a);
        }
        rep(i, 1, m + 1)
        {
            v.reset();
            ans += dfs(i);
        }
        if (ans == 0) {
            cout << "No Solution!" << endl;
            continue;
        }
        cout << ans << endl;
        rep(i, n + 1, n + n + 1)
        {
            if (fa[i] != 0)
                cout << fa[i] << " " << i - n << endl;
        }
    }
}

收获与反思

搬运定义

图的匹配相关

图的匹配：任意两条边都没有公共端点的边的集合被称为图的一组匹配。

二分图最大匹配：在二分图中，包含边数最多的一组匹配被称为二分图的最大匹配。

对于任意一组匹配 \(S\) （边集），属于 \(S\) 的边被称为匹配边，不属于 \(S\) 的边被称为非匹配边。匹配边的端点被称为匹配点，其他节点被称为非匹配点。

如果二分图中存在一条连接两个非匹配点的路径 ，使得非匹配边与匹配边在路径上交替出现，那么称该路径是匹配 \(S\) 的增广路（也称交错路）。

增广路的性质

  1. 长度为奇数
  2. 奇数边是非匹配边，偶数边是匹配边。
  3. 如果把路径上所有边的状态（是否为匹配边）取反，那么得到的新的边集 \(S'\) 仍然是一组匹配，并且匹配的边数增加了 \(1\) 。

匈牙利算法（增光路算法）

主要过程：

  1. 设 \(S\)为空集，即所有边都是非匹配边。
  2. 寻找增广路 path ，把 path 上所有边的匹配状态取反，得到一个更大的匹配 \(S'\)。（利用增光路性质3）
  3. 重复第 2 步，直至图中不存在增广路。

寻找增广路

依次尝试给每一个左部节点 xx 寻找一个匹配的右部节点 yy 。

dfs方法。

常有两种写法

  1. 单标记，邻接表写法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int dfs(int x)
    {
        rep(i, 0, e[x].size())
        {
            int y = e[x][i];
            if (v[y])
                continue;
            v[y] = 1;
            if (!fa[y] || dfs(fa[y])) {
                fa[y] = x;
                return 1;
            }
        }
        return 0;
    }

  2. 双标记，数组写法

1
2
3
4
5
6
7
8
9
10
11
12
int dfs(int x){
    rep(i,0,n){
        if(!mmp[x][i] || v[i]) continue;
        v[i] =1;
        if(!fa[i] || dfs(fa[i])){
            fa[i] = x;
            fa[x] = i; //双标记
            return 1;
        }
    }
    return 0;
}

双标记对于访问二分图里所有点得到的匹配是实际值，单标记访问所有点得到的匹配是2倍，如果访问一个集合点则是实际值，单标记更多用于两集和已被分隔开的情况。