UOJ Logo Leo_h的博客

博客

二分图最大匹配

2016-11-15 21:03:08 By Leo_h

二分图匹配-匈牙利算法

问题简介

二分图匹配的问题,一般是将点分为两个集合,两个集合之间有点连边。匹配的定义是任意两条边都没有公共点,求最大能保留的边数 模板题:UOJ78 ~(高杨大神好厉害瞬间AC)~

思路描述

先介绍一个概念叫增广路,即由非匹配边(在操作之前没有被选中的边)和匹配边交替组成的路径,其中开头和结尾都是非匹配边,因此,交换增广路匹配边和非匹配边,就会在保证已经匹配的点都有新的匹配边连接的同时,增加一条匹配边。KM算法就是根据这个思路

代码

#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
#define maxn 503
int nl,nr,m,ans;
int match[maxn];
int anti[maxn];
bool vzt[maxn];
vector<int> e[maxn];
bool find_match(int u)
{
    int s=e[u].size();
    for(int i=0;i<s;i++)
    {
        int v=e[u][i];
        if(!vzt[v])
        {
            vzt[v]=true;
            if(!match[v]||find_match(match[v]))
            {
                match[v]=u;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    scanf("%d%d%d",&nl,&nr,&m);
    for(int i=1;i<=m;i++)
    {
        int v,u;
        scanf("%d%d",&v,&u);
        e[v].push_back(u);
    }
    for(int i=1;i<=nl;i++)
    {
        memset(vzt,0,sizeof(vzt));
        if(find_match(i))ans++;
    }
    printf("%d\n",ans);
    for(int i=1;i<=nr;i++)
        anti[match[i]]=i;
    for(int i=1;i<=nl;i++)
        printf("%d ",anti[i]);
}

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。