//一般圖最大匹配,鄰接陣形式,復雜度O(n^3)
//返回匹配頂點對數,match返回匹配,未匹配頂點match值為-1
//傳入圖的頂點數n和鄰接陣mat
#define MAXN 100

int aug(int n,int mat[][MAXN],int* match,int* v,int now){
	int i,ret=0;
	v[now]=1;
	for (i=0;i<n;i++)
		if (!v[i]&&mat[now][i]){
			if (match[i]<0)
				match[now]=i,match[i]=now,ret=1;
			else{
				v[i]=1;
				if (aug(n,mat,match,v,match[i]))
					match[now]=i,match[i]=now,ret=1;
				v[i]=0;
			}
			if (ret)
				break;
		}
	v[now]=0;
	return ret;
}

int graph_match(int n,int mat[][MAXN],int* match){
	int v[MAXN],i,j;
	for (i=0;i<n;i++)
	v[i]=0,match[i]=-1;
	for (i=0,j=n;i<n&&j>=2;)
		if (match[i]<0&&aug(n,mat,match,v,i))
			i=0,j-=2;
		else
			i++;
	for (i=j=0;i<n;i++)
		j+=(match[i]>=0);
	return j/2;
}