/****************************************************
*   二分圖匹配匈牙利算法
*   擴展：1、左右端點數(shù)相同且等于匹配數(shù)稱完備匹配
*         2、有向圖的最小路徑覆蓋數(shù)是點數(shù)-最大匹配數(shù)
*
*****************************************************/
#include <iostream>
#include <cstdio>
using namespace std;
int const MAXN = 250;
int graph[MAXN][MAXN], cnt[MAXN];
//鄰接表矩陣，點度
bool ck[MAXN];//記錄是否被訪問
int match[MAXN];//匹配數(shù)組，記錄右端到左端的匹配
int V, E;//點數(shù)、邊數(shù)
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)
{//傳入矩陣和左端點數(shù)，傳出匹配的對數(shù)
    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;
}