//二分圖最大匹配,hungary算法,鄰接表形式,鄰接陣接口,復(fù)雜度O(m*e)s
//返回最大匹配數(shù),傳入二分圖大小m,n和鄰接陣
//match1,match2返回一個(gè)最大匹配,未匹配頂點(diǎn)match值為-1

#include <string.h>
#include <vector>
#define MAXN 310
#define _clr(x) memset(x,0xff,sizeof(int)*MAXN)

int hungary(int m,int n,int mat[][MAXN],int* match1,int* match2){
	int s[MAXN],t[MAXN],p,q,ret=0,i,j,k,r;
	vector<int> e[MAXN];
	//生成鄰接表(只需一邊)
	for(i=0;i<m;++i)
		for(j=0;j<n;++j)
			if (mat[i][j]) e[i].push_back(j);
	for (_clr(match1),_clr(match2),i=0;i<m;ret+=(match1[i++]>=0))
		for (_clr(t),s[p=q=0]=i;p<=q&&match1[i]<0;p++)
			for(r=0,k=s[p];r<e[k].size()&&match1[i]<0;++r)
				if (t[j=e[k][r]]<0){
					s[++q]=match2[j],t[j]=k;
					if (s[q]<0)
						for (p=j;p>=0;j=p)
							match2[j]=k=t[j],p=match1[k],match1[k]=j;
				}
	return ret;
}