二分图最大匹配

其实我很久之前就想写二分图的匈牙利算法，因为蛋疼的网络流算法写起来很不顺心……而且遇到某些特殊问题当然用特殊方法会有更好的效果啦。

匈牙利算法写起来还是很简单的，基本上理解了交错路之后就OK了。

我用的是邻接表实现。

算法思想：

1.置空res数组，表示全都没有匹配

2.从1到n1找增广路径，如果有的就ans++

3.对于k号找路径的话，就列出所有与k关联的顶点j，筛选出j没有在增广路径或者顶点j已经匹配的但仍然找到增广路径，j的匹配记为k。

/*******************************************************************************/
/* OS           : 3.2.0-58-generic #88-Ubuntu SMP Tue Dec 3 UTC 2013 GNU/Linux
 * Compiler     : g++ (GCC)  4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5)
 * Encoding     : UTF8
 * Date         : 2014-04-06
 * All Rights Reserved by yaolong.
*****************************************************************************/
/* Description: ***************************************************************
*****************************************************************************/
/* Analysis: ******************************************************************
*****************************************************************************/
/*****************************************************************************/

#include <iostream>
#include <cstring>
#include<vector>
#include<vector>
#include<cstdio>
using namespace std;
#define N 500
int n1,n2,m; //n1为A集合数，n2为B集合数,m为边数
bool stat[N];  //是否被覆盖
int res[N];    //匹配点
class Vertex
{

public:
    Vertex(int n)
    {
        link_v.resize(n);
    }
    Vertex()
    {

    }
    vector<int> link_v;

};

vector<Vertex> mp;
bool find(int k)
{
    vector<int> ::iterator itr=mp[k].link_v.begin();
    vector<int> ::iterator itr_end=mp[k].link_v.end();
    while(itr!=itr_end)
    {
        if(stat[*itr]==0)   //未标记=>不在增长路径
        {
            stat[*itr]=1;
            if(res[*itr]==0   //未匹配点
                    ||find(res[*itr]))   //还有增长路径
            {
                res[*itr]=k;    //标记*itr =k
                return true;


            }


        }
        itr++;
    }


    return false;
}
int Hungry()
{
    int ans=0;
    memset(res,0,sizeof(res));

    for(int i=1; i<=n1; i++)
    {
        memset(stat,0,sizeof(stat));
        if(find(i)) ans++;

    }
    return ans;

}
int main()
{

    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int t1,t2;

    while(cin>>n1>>n2)
    {
        mp.clear();
        mp.resize(n1+n2+1);

        cin>>m;
        for (int i=0; i<m; i++)
        {
            cin>>t1>>t2;
            mp[t1].link_v.push_back(t2);   //邻接表无向边
            mp[t2].link_v.push_back(t1);

        }
        cout<<Hungry()<<endl;
    }



fclose(stdin);
fclose(stdout);


return 0;

}

后来找一道裸题，POJ1274试验了一下，稍微改动了一下输入格式，轻松AC了。

/*******************************************************************************/
/* OS           : 3.2.0-58-generic #88-Ubuntu SMP Tue Dec 3 UTC 2013 GNU/Linux
 * Compiler     : g++ (GCC)  4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5)
 * Encoding     : UTF8
 * Date         : 2014-04-06
 * All Rights Reserved by yaolong.
*****************************************************************************/
/* Description: ***************************************************************
*****************************************************************************/
/* Analysis: ******************************************************************
*****************************************************************************/
/*****************************************************************************/

#include <iostream>
#include <cstring>
#include<vector>
#include<vector>
#include<cstdio>
using namespace std;
#define N 500
int n1,n2,m; //n1为A集合数，n2为B集合数,m为边数
bool stat[N];
int res[N];
class Vertex
{

public:
    Vertex(int n)
    {
        link_v.resize(n);
    }
    Vertex()
    {
        link_v.clear();
    }
    vector<int> link_v;

};

vector<Vertex> mp;
bool find(int k)
{
    vector<int> ::iterator itr=mp[k].link_v.begin();
    vector<int> ::iterator itr_end=mp[k].link_v.end();
    while(itr!=itr_end)
    {
        if(stat[*itr]==0)   //未标记=>不在增长路径
        {
            stat[*itr]=1;
            if(res[*itr]==0   //未匹配点
                    ||find(res[*itr]))   //还有增长路径
            {
                res[*itr]=k;    //标记*itr =k
                return true;


            }


        }
        itr++;
    }


    return false;
}
int Hungry()
{
    int ans=0;
    memset(res,0,sizeof(res));

    for(int i=1; i<=n1; i++)
    {
        memset(stat,0,sizeof(stat));
        if(find(i)) ans++;

    }
    return ans;

}
int main()
{


    int t1,t2;

    while(cin>>n1>>n2)
    {
        mp.clear();
        mp.resize(n1+n2+1);


        for(int j=1;j<=n1;j++){
         cin>>m;
        for (int i=0; i<m; i++)
        {
            cin>>t1;
            mp[n1+t1].link_v.push_back(j);
            mp[j].link_v.push_back(n1+t1);

        }
        }
        cout<<Hungry()<<endl;
    }



return 0;

}

二分图最大匹配,布布扣,bubuko.com

二分图最大匹配

原文：http://blog.csdn.net/dengyaolongacmblog/article/details/23035953