二分图 & 最大匹配 & 匈牙利算法

定义

二分图

对于一个无向图 $G=(V, E)$,可以将 $V$ 分为两个不相交的子集,使得任意一条边的顶点分属两个不同的点集,那么这个无向图是二分图。

匹配

对于无向图 $G=(V, E)$,取边集的子集 $E^*$,使得 $E^*$ 中任意两条边没有公共顶点,那么 $E^*$ 是图 $G$ 的一个匹配,又称边独立集。

最大匹配

边数最多的匹配。极大匹配的边数唯一,取法可能不唯一。

匹配边 & 非匹配边

在边独立集中的边是匹配边,反之是非匹配边。

匹配点 & 非匹配点

能被匹配边连接到的点是匹配点,反之是非匹配点。

完美匹配

若 $M$ 是图 $G$ 的一个匹配,且 $G$ 中的每个顶点都是匹配点,那么 $M$ 是 $G$ 的完美匹配。

交错路径

图 $G$ 中,由匹配边和非匹配边交替构成的路径,是交错路径。

增广路径

起点和终点都是非匹配点的交错路径,是增广路径。

显然,$M$ 是 $G$ 的最大匹配,当且仅当 $G$ 中不含关于 $M$ 的增广路径。

因为如果 $G$ 中含有关于 $M$ 的增广路径,把增广路径上的匹配边取反,可以使匹配大小增加$1$.

二分图最大匹配

概述

在二分图中找到一个最大匹配。

Hall定理

二分图 $G = $ < $V_1, V_2, E$ >,其中 $|V_1| \leq |V_2|$,$G$ 中存在 $V_1$ 到 $V_2$ 的完美匹配,当且仅当 $V_1$ 中任意 $k\in [1, |V_1|]$ 个顶点,都至少与 $V_2$ 中的 $k$ 个顶点相连。

反证即可。

思想

对一条增广路进行异或之后,能使匹配中的边数增加 $1$.

异或之后,可以得到:

匈牙利算法

  1. 将初始的匹配 $M$ 置为 $\emptyset$.
  2. 找到一条增广路径,通过异或操作更新最大匹配。
  3. 重复2.

时间复杂度:$\mathcal{O}(EV)$

代码(From Jisuanke):

const int MAX_N = 100;
const int MAX_M = 10000;
struct Edge {
    int v, next;
} e[MAX_M];
int p[MAX_N], eid;
void init() {
    memset(p, -1, sizeof(p));
    eid = 0;
}
void insert(int u, int v) {
    e[eid].v = v;
    e[eid].next = p[u];
    p[u] = eid++;
}
bool vst[MAX_N];
int rmatch[MAX_N];
bool dfs(int u) {
    for(int i = p[u]; i != -1; i = e[i].next) {
        int v = e[i].v;
        if(!vst[v]) {
            vst[v] = true;
        	if(rmatch[v] == -1 || dfs(rmatch[v])) {
                rmatch[v] = u;
                return true;
            }
        }
    }
    return false;
}
int hungary(int n) {
    int cnt = 0;
    memset(rmatch, -1, sizeof(rmatch));
    for(int i = 1; i <= n; i++) {
        memset(vst, 0, sizeof(vst));
        cnt += dfs(i);
    }
    return cnt;
}
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇
window.pjaxLoaded = function(){ } window.pjaxLoaded();