二分图最大匹配匈牙利算法（poj）3041（模板）-蒲公英云

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

给出一个图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;
}