Chlience

【算法】二分图 & 匈牙利算法的简单小结
什么是二分图?简单来说,二分图指顶点可以分成两个不相交的集合 $U$ 和 $V$ ,使得在同一集合内的顶点不相邻的...
扫描右侧二维码阅读全文
21
2018/10

【算法】二分图 & 匈牙利算法的简单小结

什么是二分图?

简单来说,二分图指顶点可以分成两个不相交的集合 $U$ 和 $V$ ,使得在同一集合内的顶点不相邻的的图

设 $G = (V,E)$ ,若顶点 $V$ 可分为两个相交的子集 $(U,V)$ ,且对于图中的每条边 $(i,j)$ 所连接的两个顶点 $i$ 和 $j$ 分别属于这两个不同的顶点集 $(i \in U , j \in V)$ ,则称图 $G$ 为一个二分图

当然,用染色的方法理解也是可以的:如果能将每个节点染上两种颜色中的一种,并且同一颜色节点不相邻,则原图为二分图

据此,我们可以得知一个图 $G$ 是二分图的充分必要条件:所有回路长度均为偶数

二分图的一些性质

  • 最小边覆盖集的基数等于最大独立集的基数
  • 最大独立集的基数与最大匹配的基数之和,等于顶点数目
  • 连通的二分图:

    • 最小顶点覆盖集的基数等于最大匹配的基数

关于二分图匹配的前置小知识

匹配: 一个边集,其中任意两条边没有公共顶点
匹配边: 一个匹配中的边
匹配点: 一个匹配中边的顶点

最大匹配: 一个图所有匹配中,所含边数最多的匹配
完美匹配: 所有顶点都是匹配点,则为完美匹配

求解二分图匹配问题

一般我们使用 匈牙利算法 或者 网络流 来解决二分图匹配问题
这里主要介绍匈牙利算法,网络流可能在后面的题目中会讲到

交替路: 从某个 未匹配点 出发,依次经过非匹配边,匹配边,非匹配边...所形成的路径
假设刚开始的点属于 $u$ ,显然这个路径上点所属集合为 $u->v->u->...$

增广路: 从一个未匹配点出发的交替路若途径另外一个非匹配点,则这条交替路称为增广路

在增广路上,至少有两个非匹配点和一堆匹配点,那么路径两端必然是两条非匹配边,中间必然为 匹配->非匹配->匹配...交替,即非匹配边要比匹配边多一条
那么我们将匹配/非匹配边交换,即能得到多一条匹配边的匹配,路径上的点全部成为匹配点
而且因为中间的点显然都是匹配点,与这条增广路外的点不存在任何匹配边,所以仍然满足匹配的性质

可以证明,$M$ 是最大匹配的充要条件是 $G$ 中无 $M$ 的可增广路

这个东西在 1957 年由 Claude Berge 证明

再来个定理:如果从某个点 $A$ 出发,没有找到增广路径,那么从任意点出发,找到任意增广路径来改变现在的匹配,从 $A$ 出发也无法找到增广路径

可以使用这个定理来进行匈牙利算法的改进,减少很多不必要的运算量

最终的板子就是这样的啦!

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
struct edge {int t , n;}e[N * N];
int head[N] , tot;
void addedge(int u , int v) {
    ++ tot;
    e[tot].t = v;
    e[tot].n = head[u];
    head[u] = tot;
}

int match[N];
int use[N];
int n , m , E , ans;
int times;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
bool dfs(int x) {
    for(int i = head[x] ; i ; i = e[i].n) {
        if(use[e[i].t] != times) {
            use[e[i].t] = times;
            if(!match[e[i].t] || dfs(match[e[i].t])) {
                match[e[i].t] = x;
                return true;
            }
        }
    }
    return false;
}
int main() {
    n = read();
    m = read();
    E = read();
    for(int i = 1 ; i <= E ; ++ i) {
        int x = read() , y = read();
        if(y > m) continue;
        addedge(x , y);
    }
    for(int i = 1 ; i <= n ; ++ i) {
        ++ times;
        if(dfs(i))
            ++ ans;
    }
    printf("%d\n" , ans);
    return 0;
}
Last modification:October 22nd, 2018 at 07:46 am

Leave a Comment