二分图最大匹配匈牙利算法（poj）3041（模板）

喜欢ヅ旅行 2022-08-27 04:55 183阅读 0赞

给出一个图G=（V，E）

概念：

**匹配：在图G中两两没有公共端点的边的集合**

**最大匹配：选出尽量多的边，使得任意两条选中的边均没有公共端点。**

**边覆盖：G中的任意顶点都至少是F中某条边的端点的边的集合**

**最小边覆盖：选出尽量少的边，使得G中的任意顶点都至少是选出的边的某个端点。**

**顶点覆盖：在图G中的任意边都有至少一个端点属于S的顶点集合。**

**最小顶点覆盖：选出尽量少的顶点，使得图G中的任意边都有至少一个端点属于S的顶点集合。**

**独立集：在G中两两互不相连的顶点集合。**

**最大独立集：选出尽量多的顶点，使得在G中两两互不相连、**

**定义：对于不存在独立点的图， 最大匹配 + 最小边覆盖 = E（所有边的集合）**

**定义：最大独立集 + 最小点集覆盖 = V（所有顶点集合）**

**定义：在二分图中，最大匹配 = 最小点集覆盖**

二分图最大匹配：http://blog.csdn.net/y990041769/article/details/8812042

**算法思想：从所有点出发，如果某个点还没有匹配，找与之相连的另一边没有匹配的点，如果都匹配了，那么找看能不能让其他的点增广到另一个点，把当前点让出来给这个点。**

邻接表模板：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    using namespace std;
    const int N = 1100;
    int V,m;
    int match[N];
    vector<int> map[N];
    bool used[N];
    
    void add_edge(int u,int v)
    {
        map[u].push_back(v);
        map[v].push_back(u);
    }
    bool dfs(int v)
    {
        used[v]=true;
        for(int i=0;i<map[v].size();i++)
        {
            int u=map[v][i],w=match[u];
            if(w<0 || !used[w]&&dfs(w))
            {
                match[v]=u;
                match[u]=v;
                return true;
            }
        }
        return false;
    }
    int bipartite_matchint()
    {
        int res=0;
        memset(match,-1,sizeof(match));
        for(int v=0;v<V;v++)
        {
            if(match[v]<0){
                memset(used,0,sizeof(used));
                if(dfs(v))
                    res++;
            }
        }
        return res;
    }
    int main()
    {
        int n;
        while(~scanf("%d%d",&n,&m))
        {
            V=2*n;
            for(int i=0;i<m;i++){
                int x,y;
                scanf("%d%d",&x,&y);
                add_edge(x,n+y);
            }
            printf("%d\n",bipartite_matchint());
        }
        return 0;
    }

邻接矩阵模板：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    const int N = 1100;
    int n,m;
    int link[N],vis[N],map[N][N];
    bool dfs(int x)
    {
        for(int i=1; i<=n; i++)
        {
            if(map[x][i]==1 && vis[i]==0)
            {
                vis[i]=1;
                if(link[i]==0 || dfs(link[i]))
                {
                    link[i]=x;
                    return true;
                }
                //vis[i]=0;   //搞不懂加上这个会超时
            }
        }
        return false;
    }
    int bipartite_link()  //求最大匹配
    {
        memset(link,0,sizeof(link));
        int count=0;
        for(int i=1; i<=n; i++)
        {
            memset(vis,0,sizeof(vis));
            if(dfs(i))
                count++;
        }
        return count;
    }
    int main()
    {
        while(~scanf("%d%d",&n,&m))
        {
            memset(map,0,sizeof(map));
            for(int i=0; i<m; i++)
            {
                int x,y;
                scanf("%d%d",&x,&y);
                map[x][y]=1;
            }
            printf("%d\n",bipartite_link());
        }
        return 0;
    }