匈牙利.cpp

匈牙利算法,求解二分图最大匹配的一个时间复杂度与程序复杂度折中的算法

#include <iostream.h>
#include <string.h>

int match[100];
int n;
char a[100][100];

int find(int k)
{
	int st,sf,i,j,t;
	int q[100];
	int f[100];
	q[1] = k,st = 1,sf = 1;
	memset(f,0,sizeof f);
	while (st<=sf)
	{
		for(i=1;i<=n;i++)
			if (!f[i] && a[q[st]][i])
			{
				if (match[i])
				{
					sf++;
					q[sf] = match[i];
					f[i] = q[st];
				}
				else 
				{
					j = q[st];
					while(1)
					{
						t = match[j];
						match[j] = i;
						match[i] = j;
						if (!t) break;
						i = t;
						j = f[t];
					}
					return 1;
				}
			}
			st++;
	}
	return 0;
} 

int main()
{
	a[1][6] = a[6][1] = 1;
	a[2][5] = a[5][2] = 1;
	a[2][7] = a[7][2] = 1;
	a[3][6] = a[6][3] = 1;
	a[4][7] = a[7][4] = 1;
	n = 8;
	int i,all = 0;
	for(i=1;i<=n;i++) if (!match[i])
	{
		all+=find(i);
	}
	cout<<all<<endl;
	return 0 ;
}