二分图匹配.cpp

本人参加ACM竞赛使用的一些算法模板

/****************************************************
*   二分图匹配匈牙利算法
*   扩展：1、左右端点数相同且等于匹配数称完备匹配
*         2、有向图的最小路径覆盖数是点数-最大匹配数
*
*****************************************************/
#include <iostream>
#include <cstdio>
using namespace std;
int const MAXN = 250;
int graph[MAXN][MAXN], cnt[MAXN];
//邻接表矩阵，点度
bool ck[MAXN];//记录是否被访问
int match[MAXN];//匹配数组，记录右端到左端的匹配
int V, E;//点数、边数
bool search(int G[][MAXN], int k)
{//找增广边
    for(int i = 0; i < cnt[k]; i++)
    {
        int p = G[k][i];
        if(ck[p])
        {
            ck[p] = false;
            int t = match[p];
            if(t == -1 || search(G, t) )
            {
                match[p] = k;
                return true;
            }
            match[p] = t;
        }
    }
    return false;
}

int hungary(int G[][MAXN], int left)
{//传入矩阵和左端点数，传出匹配的对数
    int answer(0);
    int i, j;
    for(i = 0; i < V; i++)
	{
		match[i] = -1;
	}
    for(i = 0; i < left; i++)
    {
       for(j = 0; j < V; j++)
	   {
			ck[j] = true;
		}
       if(search(G, i))
       {
            ++answer;
	   }
    }
    return answer;
}