学步园

带权二分图最大匹配模板O(n^3)

const int maxn=31;
const int inf=maxint/2;
int w[maxn][maxn],x[maxn],y[maxn];
int prev_x[maxn],prev_y[maxn],son_y[maxn],slack[maxn],par[maxn];
int lx,ly,pop;
int n,k,m;
int mold[310],mnew[310],num_old,num_new;
char _old[10010],_new[10010],tmp[10];

void adjust(int v)
{
	son_y[v]=prev_y[v];
	if (prev_x[son_y[v]]!=-2)
		adjust(prev_x[son_y[v]]);
}

bool find(int v)
{
	int i;
	for (i=0; i<pop; i++)
		if (prev_y[i]==-1)
		{
			if (slack[i]>x[v]+y[i]-w[v][i])
			{
				slack[i]=x[v]+y[i]-w[v][i];
				par[i]=v;
			}
			if (x[v]+y[i]==w[v][i])
			{
				prev_y[i]=v;
				if (son_y[i]==-1)
				{
					adjust(i);
					return true;
				}
				if (prev_x[son_y[i]]!=-1)
					continue;
				prev_x[son_y[i]]=i;
				if (find(son_y[i]))
						return true;
			}
		}
	return false;
}

int km()
{
	int i,j,m;
	for (i=0; i<pop; i++)
	{
		son_y[i]=-1;
		y[i]=0;
	}
	for (i=0; i<pop; i++)
	{
		x[i] =0;
		for (j = 0; j < pop; j ++)
			x[i] = max(x[i],w[i][j]);
	}
	bool flag;
	for ( i=0; i < pop; i ++){
		for (j=0;j<pop;j++){
			prev_x[j]=prev_y[j]=-1;
			slack[j] = inf;
		}
		prev_x[i] = -2;
	if (find(i)) continue;
	flag = false;
	while (!flag){
		m=inf;
		for (j=0;j<pop;j++)
			if (prev_y[j]==-1)
				m=min(m,slack[j]);
		for (j=0;j<pop;j++){
			if (prev_x[j]!=-1)
				x[j]-=m;
			if (prev_y[j]!=-1)
				y[j]+=m;
			else slack[j]-=m;
		}
		for (j=0;j<pop;j++)
			if (prev_y[j]==-1 && !slack[j]){
				prev_y[j]=par[j];
				if (son_y[j]==-1){
					adjust(j);
					flag=true;
					break;
				}
				prev_x[son_y[j]]=j;
				if (find(son_y[j])){
					flag=true;
					break;
				}
			}
		}
	}
	int ans=0;
	for(int i=0;i<pop;i++)
	   ans+=w[son_y[i]][i];
	return ans;
}

memset(w,0,sizeof(w));//不要求完全匹配时，每次调用都要初始化为0</strong></strong>

接口：

int km();

复杂度：O(n^3),n为图的点数

输入：w[i][j] 全局变量，邻接矩阵，表示i到j的权值 

pop 全局变量，表示图的点数

输出： son_y[i] 全局变量，表示匹配方案

注意：

1.KM算法运行要求必须是左右点数相同（即存在完全匹配）；

如果只求最大权匹配（不一定完备），将不存在的边权赋值为0，并在少的一侧添加虚拟节点（即所有的边）；

2.求最小权匹配将边权取相反数即可。

题目：hdu3718 ACM
带权二分图匹配 hdu3718

参考：https://www.byvoid.com/blog/match-km/