二分图最大匹配

AngelNH

发布于 2020-04-16 15:40:37

1.1K0

发布于 2020-04-16 15:40:37

文章被收录于专栏：AngelNIAngelNI

二分图

二分图也叫二部图，设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。如下图所有的顶点可以分成A，B两个集合，而A集合与B集合中的点与自己的阵营的点是没有连线的（A集合的点只与B集合的点有边相连），则称这个为一个二分图.(离散数学中的内容)

点覆盖：对于图G=(V,E)中的一个点覆盖是一个集合S⊆V使得每一条边至少有一个端点在S中。最小点覆盖：点个数最少的S集合。

二分图的最大匹配的含义，就是说在这A，B两个集合中不断选择两个存在连线（只有存在连线才能连起来，而且每个点只能匹配一次）的两个点相连，求最多可以有多少条连线即这个二分图的最大匹配数

可以参考二分图匹配，生动有趣的文章。

性质

定义和定理：
    最大匹配数：最大匹配的匹配边的数目
    最小点覆盖数：选取最少的点，使任意一条边至少有一个端点被选择
    最大独立数：选取最多的点，使任意所选两点均不相连
    最小路径覆盖数：对于一个 DAG（有向无环图），选取最少条路径，使得每个顶点属于且仅属于一条路径。路径长可以为 0（即单个点）。

    定理1：最大匹配数 = 最小点覆盖数（这是 Konig 定理）
    定理2： 最大独立数与最小点覆盖数互补
    定理3：最小路径覆盖数 = 顶点数 - 最大匹配数

匈牙利算法

匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。

增广路径

若图G中一条连通两个未匹配顶点的路径，并且属于M的边和不属于M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径（举例来说，有A、B集合，增广路由A中一个点通向B中一个点，再由B中这个点通向A中一个点……交替进行）。

匈牙利算法:
    算法轮廓：
    1. 置M为空
    2. 找出一条增广路径P，通过取反操作获得更大的匹配M’代替M
    3. 重复2操作直到找不出增广路径为止
增广路径:
    我们采用DFS的办法找一条增广路径： 
        从A部一个未匹配的顶点u开始，找一个未访问的邻接点v（v一定是B部顶点）。对于v，分两种情况：
            1.如果v未匹配，则已经找到一条增广路
            2.如果v已经匹配，则取出v的匹配顶点w(w一定是A部顶点)，边(w,v)目前是匹配的，根据“取反”的想法，要将(w,v)改为未匹配，(u,v)设为匹配，能实现这一点的条件是看从w为起点能否新找到一条增广路径P’。如果行，则u-v-P’就是一条以u为起点的增广路径。

练习

HDU2306

模板题

#include<iostream>
#include<cstring>
using namespace std;
const int N = 510;
int map[N],vis[N];
int pp[N][N];
int n,m,k;
int dfs(int x)
{
    //对另一个集合进行查找
    for(int i =1;i<=m;++i)
    {
        if(!vis[i]&&pp[x][i])
        {
            vis[i] = 1;
            if(!map[i]||dfs(map[i]))
            {
                map[i] =x;
                return 1;
            }
        }
        else
        {
            continue;
        }
        
    }
    return 0;
}
int main()
{
    while(cin>>k&&k)
    {
        int ans = 0;
        memset(map,0,sizeof(map));
        memset(pp,0,sizeof(pp));
        cin>>n>>m;
        for(int i =1;i<=k;++i)
        {
            int a,b;
            cin>>a>>b;
            pp[a][b] = 1;
        }
        for(int i =1;i<=n;++i)
        {
            memset(vis,0,sizeof(vis));
            if(dfs(i))
                ans++;
        }
        cout<<ans<<endl;
    }
    system("pause");
    return 0;
}

LuoguP3386

模板题

#include<iostream>
#include<cstring>
using namespace std;

const int N = 1010;

int map[N],vis[N],pp[N][N];
int k,n,m;
int dfs(int x)
{
    for(int i =1;i<=m;++i)
    {
        if(!vis[i]&&pp[x][i])
        {
            vis[i] = 1;
            if(!map[i]||dfs(map[i]))
            {
                map[i] = x;
                return 1;
            }
        }
        else
        {
            continue;
        }
        
    }
    return 0;
}
int main()
{
    cin>>n>>m>>k;
    memset(map,0,sizeof(map));
    memset(pp,0,sizeof(pp));
    for(int i =1;i<=k;++i)
    {
        int a,b;
        cin>>a>>b;
        pp[a][b] = 1;
    }
    int ans=0;
    for(int i=1;i<=n;++i)
    {
        memset(vis,0,sizeof(vis));
        if(dfs(i))
            ans++;
    }
    cout<<ans<<endl;
    system("pause");
    return 0;
}

HDU1083

#include<iostream>
#include<cstring>
using namespace std;
const int N = 310;
int mp[N],vis[N],pp[N][N];
int n,m,k,t;
int dfs(int x)
{
    for(int i =1;i<=m;++i)
    {
        if(!vis[i]&&pp[x][i])
        {
            vis[i] =1;
            if(!mp[i] || dfs(mp[i]))
            {
                mp[i] = x;
                return 1;
            }
        }
        else
        {
            continue;
        }
        
    }
    return 0;
}
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        memset(mp,0,sizeof(mp));
        memset(pp,0,sizeof(pp));
        for(int i =1;i<=n;++i)
        {
            cin>>k;
            while(k--)
            {
                int a;
                cin>>a;
                pp[i][a] =1;
            }
        }
        int ans = 0;
        for(int i =1;i<=n;++i)
        {
            memset(vis,0,sizeof(vis));
             if(dfs(i))
                ans++;
        }
        if(ans == n)
            puts("YES");
        else
        {
            puts("NO");
        }
        
    }
    system("pause");
    return 0;
}

poj3041

在这里用到性质里的内容，最小覆盖数 == 最大匹配数

点覆盖

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 600;
const int NN = 1e5+10;
int mp[NN],vis[NN],pp[N][N];
int n,k;
int dfs(int x)
{
    for(int i =1;i<=n;++i)
    {
        if(!vis[i]&&pp[x][i])
        {
            vis[i] = 1;
            if(!mp[i]||dfs(mp[i]))
            {
                mp[i] = x;
                return 1;
            }
        }
        else
        {
            continue;
        }
        
    }
    return 0;
}
int main()
{
    cin>>n>>k;
    memset(mp,0,sizeof(mp));
    memset(pp,0,sizeof(pp));
    for(int i =1;i<=k;++i)
    {
        int a,b;
        cin>>a>>b;
        pp[a][b] = 1;
    }
    int ans = 0;
    for(int i =1;i<=n;++i)
    {
        memset(vis,0,sizeof(vis));
        if(dfs(i))
            ans++;
    }
    cout<<ans<<endl;
    system("pause");
    return 0;
}

poj3020

感觉这道有点复杂，用到了 最小路径覆盖数 = 顶点数 - 最大匹配数，如何构造二分图，如何拆点。

引用一句话 “ 匈牙利算法解题是极为简单的，但是图论的难并不是难在解答，而是建图的过程，也难怪会有牛曰：用匈牙利算法，建图是痛苦的，最后是快乐的。”

贴上一个讲的比较好的文章传送门

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 410;

int pp[N][N],lk[N],vis[N];

int mapp[42][42];

int h,w;
int d[4][2] = {-1,0,1,0,0,-1,0,1};
int con;
int dfs(int x)
{
    for(int i =1;i<=con;++i)
    {
        if(!vis[i]&&pp[x][i])
        {
            vis[i] = 1;
            if(!lk[i]||dfs(lk[i]))
            {
                lk[i] = x;
                return 1;
            }

        }
        // else
        // {
        //     continue;
        // }
        
    }
    return 0;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>h>>w;
        con = 0;
        memset(lk,0,sizeof(lk));
        memset(mapp,0,sizeof(mapp));
        memset(pp,0,sizeof(pp));
        char ch;
        for(int i =1;i<=h;++i)
        {
            for(int j =1;j<=w;++j)
            {
                
                cin>>ch;
                if(ch == '*')
                    mapp[i][j] = ++con;
            }
        }
        for(int i =1;i<=h;++i)
        {
            for(int j =1;j<=w;++j)
            {
                if(mapp[i][j])
                {
                    for(int k =0;k<4;++k)
                    {
                        int x = i + d[k][0];
                        int y = j + d[k][1];
                        if(mapp[x][y])
                        {
                            pp[mapp[i][j]][mapp[x][y]] = 1;
                        }
                    }
                }
            }
        }
        int ans=0;
        for(int i =1;i<=con;++i)
        {
            memset(vis,0,sizeof(vis));
            if(dfs(i))
                ans++;
        }
        //最小路径覆盖数 = 顶点数 - 最大匹配数
        cout<<con-ans/2<<endl;
    }
    system("pause");
    return 0;
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2020-02-28|，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

腾讯云开发者社区

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

腾讯云开发者社区

登录后参与评论

0 条评论

热度