2018-03-12

二分图的最大匹配

最朴素的二分图的匹配方法：增广路算法。不断的使用dfs去寻找增广路，感觉效率很低。
还有一堆的等价的式子，有待进一步的补充：

二分图最小顶点覆盖数 = 二分图最大匹配数
DAG的最小路径覆盖数 = V - 二分图最大匹配数
二分图的最大独立集数 = V - 二分图最大匹配数
要能理解其中的证明，并且灵活的进行相应的转换，emmmmmmmmmmmmmmm

二分图的最大匹配

只要就是匈牙利算法，不断的使用dfs寻找增广路进行相应的扩充。

第二种求法就是建立相应的网络流模型，然后跑最大流，最大流就是匹配的最大的边数。

二分图的一些等价式

最小点覆盖 = 最大二分匹配
简单的证明：

题目

E - Kindergarten POJ - 3692

题意

女生和女生之间相互认识，男生和男生之间相互认识，然后给出n对女生、男生之间的关系，这些男生女生之间相互认识。
问最大能选出来多少个人，使得他们之间相互的认识。

题解

不认识的人之间连边，求最大独立集。
最大独立集 = 节点数-二分匹配数

AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 205;
bool mp[maxn][maxn];
int G, B, n;
bool vis[maxn];
int adj[maxn];
int kase;
void init(){
    memset(vis, 0, sizeof(vis));
    memset(adj, -1, sizeof(adj));
    for(int i=0; i<maxn; i++)
        for(int j=0; j<maxn; j++) mp[i][j] = true;
}
bool dfs(int u){
    for(int i=1; i<=B; i++){
        if(!vis[i]&&mp[u][i]){
            vis[i] = true;
            if(adj[i] == -1||dfs(adj[i])){
                adj[i] = u;
                return true;
            }
        }
    }
    return false;
}
void solve(){
    int ans = 0;
    for(int i=1; i<=G; i++){
        memset(vis, 0, sizeof(vis));
        if(dfs(i)) ans++;
    }
    cout<<"Case "<<++kase<<": "<<G+B-ans<<endl;
}
int main()
{
    while(~scanf("%d%d%d", &G, &B, &n)&&(G+B+n)){
        init();
        int g, b;
        for(int i=0; i<n; i++){
            scanf("%d%d", &g, &b);
            mp[g][b] = false;
        }
        solve();
    }
    return 0;
}

题目

二分图的模板题

AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
vector<int> G[maxn*2];
int match[maxn*2];
int used[maxn*2];
int n, m, l;
void add_edge(int u, int v)
{
    G[u].push_back(v);
    G[v].push_back(u);
}
 
bool dfs(int v){
    used[v] = true;
    for(int i=0; i<G[v].size(); i++){
        int u = G[v][i], w = match[u];
        if(w == -1 || !used[w]&&dfs(w)){
            match[u] = v;
            match[v] = u;
            return true;
        }
    }
    return false;
}
 
void solve(){
    int ans = 0;
    memset(match, -1, sizeof(match));
    for(int v=0; v<=n; v++){
        if(match[v] == -1){
            memset(used, 0, sizeof(used));
            if(dfs(v)) ans++;
        }
    }
    for(int v=500; v<=m+500; v++){
        if(match[v] == -1){
            memset(used, 0, sizeof(used));
            if(dfs(v)) ans++;
        }
    }
    printf("%d\n", ans);
}
 
int main()
{
 
    while(~scanf("%d%d", &n, &m)){
        for(int i=0 ;i<maxn*2; i++) G[i].clear();
        scanf("%d", &l);
        for(int i=1; i<=l; i++){
            int u, v;
            scanf("%d%d", &u, &v);
            add_edge(u, v+500);
        }
        solve();
        //cout<<match[1]<<" "<<match[2]<<" "<<match[501]<<" "<<match[502]<<endl;
    }
    return 0;
}

二分图的最大团

二分图的最小顶点覆盖最大独立集最大团
定义：对于一般图来说，团是一个顶点集合，且由该顶点集合诱导的子图是一个完全图，简单说，就是选出一些顶点，这些顶点两两之间都有边。最大团就是使得选出的这个顶点集合最大。对于二分图来说，我们默认为左边的所有点之间都有边，右边的所有顶点之间都有边。那么，实际上，我们是要在左边找到一个顶点子集X，在右边找到一个顶点子集Y，使得X中每个顶点和Y中每个顶点之间都有边。

方法：二分图的最大团=补图的最大独立集。

补图的定义是：对于二分图中左边一点x和右边一点y，若x和y之间有边，那么在补图中没有，否则有。

这个方法很好理解，因为最大独立集是两两不相邻，所以最大独立集的补图两两相邻。

网络流进行二分图匹配

未解决的问题

本文标题:二分图的最大匹配

文章作者:Babydragon

发布时间:2018-03-12, 23:04:23

最后更新:2018-03-23, 13:30:40

原始链接:http://baolintian.github.io/2018/03/12/二分图的最大匹配/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。