You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

6.7 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

AcWing 861. 二分图的最大匹配

一、题目描述

给定一个二分图,其中左半部包含 n_1 个点(编号 1n_1),右半部包含 n_2 个点(编号 1n_2),二分图共包含 m 条边。

数据保证任意一条边的两个端点都不可能在同一部分中。

请你求出二分图的最大匹配数。

二分图的匹配:给定一个二分图 G,在 G 的一个子图 M 中,M 的边集 {E} 中的任意两条边都不依附于同一个顶点,则称 M 是一个匹配。
二分图的最大匹配:所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配,其边数即为最大匹配数。

输入格式 第一行包含三个整数 n_1n_2m

接下来 m 行,每行包含两个整数 uv,表示左半部点集中的点 u 和右半部点集中的点 v 之间存在一条边。

输出格式 输出一个整数,表示二分图的最大匹配数。

数据范围 1≤n1,n2≤500,1≤u≤n_1,1≤v≤n_2,1≤m≤10^5

输入样例:

2 2 4
1 1
1 2
2 1
2 2

输出样例:

2

二、二分图的最大匹配

  • 前提:给定一个二分图,不用你判断是不是二分图,已经明确知道是二分图,让你求它的最大匹配。

  • 定义:在一个无向图中,定义一条边覆盖的点为这条边的两个端点。 找到一个边集S包含最多的边,使得这个边集覆盖到的所有顶点中的每个顶点只被一条边覆盖。S的大小叫做图的最大匹配。

匈牙利算法

又名:【月佬算法】,目标:成就更多美满姻缘! 建立有向图G,分为二分图的左侧和右侧。 优先选择左侧序号更小的连接可能的边。 对于两个点的目标点“冲突”的时候,采取“协商”的办法。 即序号小的连接可能连接的另一条边。 若“协商”失败,则放弃序号较大的点的边。

概念看的都好绕,实例比较好懂:

你拥有的大概就是下面这样一张关系图,每一条连线都表示互有好感。

本着救人一命,胜造七级浮屠的原则,你想要尽可能地撮合更多的情侣,匈牙利算法的工作模式会教你这样做:

  1. 先试着给1号男生找妹子,发现第一个和他相连的1号女生还名花无主,got\ it,连上一条蓝线
  1. 接着给2号男生找妹子,发现第一个和他相连的2号女生名花无主,got\ it
  1. 接下来是3号男生,很遗憾1号女生已经有主了,怎么办呢? 我们试着给之前1号女生匹配的男生(也就是1号男生)另外分配一个妹子。(黄色表示这条边被临时拆掉)

1号男生相连的第二个女生是2号女生,但是2号女生也有主了,怎么办呢?我们再试着给2号女生的原配重新找个妹子(注意这个步骤和上面是一样的,这是一个递归的过程)

此时发现2号男生还能找到3号女生,那么之前的问题迎刃而解了,回溯回去

2号男生可以找3号妹子 1号男生可以找2号妹子 3号男生可以找1号妹子

所以第3步最后的结果就是

  1. 接下来是4号男生,很遗憾,按照第三步的节奏我们没法给4号男生腾出来一个妹子,我们实在是无能为力了……香吉士同学走好。

三、实现代码

#include <bits/stdc++.h>

using namespace std;
const int N = 510;
const int M = 100010;

int n1, n2;
int m;

int match[N];
int st[N];
int res;

int h[N], e[M], ne[M], idx;
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int dfs(int u) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (!st[v]) {
            st[v] = 1;
            if (match[v] == 0 || dfs(match[v])) {
                match[v] = u;
                return 1;
            }
        }
    }
    return 0;
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n1 >> n2 >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

    for (int i = 1; i <= n1; i++) {
        memset(st, 0, sizeof st);
        if (dfs(i)) res++;
    }

    printf("%d\n", res);
    return 0;
}

五、 解释int st[N]的作用

重点:st[]的作用:

首先我们find(x) 遍历属于h[x]的单链表相当于遍历他所有喜欢的女生

如果某个女生j没有被他预定过的话,就标记这个女生j被他预定,即st[j]=true

这时如果女j还没有匹配过,即match[j]==0的时候,那这个预定就成真了,得到match[j]=x

而如果女j之前就被男k匹配过了,那我们就find(k),也就是find(match[j])(因为原本match[j]==k)

然后在find(k)的过程中,因为st[j]=true,这时候男k就不能再选则女j了,因为女j已经被预定了,所以男k就只能在他喜欢的女生里面选择其他人来匹配。

当然,如果find(k)返回false的话,那就 if(match[j]==0 || find(match[j]))都不成立,那男j就一边玩去吧~