首页 > 代码库 > 二分图匹配的匈牙利算法

二分图匹配的匈牙利算法

匈牙利算法,很绕,其实写起来也就一点点长度。。

bool find(int a){	int i,j;	for(i=head[a];i;i=next[i]){		j=to[i];		//获得相邻的点		if(!unable[j]){//如果这个点可以被匹配(前一次匹配到这点时被重新分配过)			unable[j]=true;//假设这次不能匹配			if(!ub[j] || find(ub[j])){//如果可以匹配				ub[j]=a;//设值				unable[j]=false;//下一次可以				return true;//可以			}		}	}	return false;//不能}int hungary(int n){	int res=0;	for(i=0;i<n;++i){		memset(unable,sizeof unable,0);//这是必须的		if(find(i)) ++res;//如果可以找到匹配	}	return res;}

 

二分图匹配的匈牙利算法