hdu 2255二分图最大权值匹配的KM 算法

对KM的深入理解请看以下博客（写的不错的）：http://blog.sina.com.cn/s/blog_691ce2b701016reh.html

我的理解：如有错误，请大牛指正！！

1.KM（）算法实际就是一种遍历，从权值最大的开始匹配，如果成功的完备匹配了，那这个权值一定是最大的权值。因为我们是从最大的开始一点点小下来遍历的。

2.slack[  ]  这个数组 可以说是一个 松弛变量数组 ，目的是为了 增加匹配。

3.实际也没什么好讲的就是不断的增广，很多也都这样，松弛迫近，跟那什么单纯形法有想通之处。

4. 匈牙利算法进行匹配的寻找。

hdu 2255

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

const int M=400,inf=0x3f3f3f3f;
int w[M][M],link[M],lx[M],ly[M];
int nx,ny,n,slack[M];
int visx[M],visy[M];

int DFS(int x){
	visx[x]=1;
	int i;
	for(i=1;i<=ny;i++){
		if(visy[i]) continue;
		int t=lx[x]+ly[i]-w[x][i];
		if(t==0){
			visy[i]=1;
			if(link[i]==-1||DFS(link[i])){
				link[i]=x;
				return 1;
			}
		}
		else if(slack[i]>t) slack[i]=t;
	}
	return 0;
}

int KM()
{
	int i,j;
	memset(link,-1,sizeof(link));
	memset(ly,0,sizeof(ly));
	for(i=1;i<=nx;i++)
		for(j=1,lx[i]=-inf;j<=ny;j++){
			if(lx[i]<w[i][j]) lx[i]=w[i][j];
		}
	for(i=1;i<=nx;i++){
			for(j=1;j<=ny;j++) slack[j]=inf;			
			while(1){
				memset(visx,0,sizeof(visx));
				memset(visy,0,sizeof(visy));
				if(DFS(i)) break;
				int d=inf;
				for(j=1;j<=ny;j++) 
					if(!visy[j]&&slack[j]<d)
						d=slack[j];
				for(j=1;j<=nx;j++)
					if(visx[j]) 
						lx[j]-=d;
				for(j=1;j<=ny;j++)
					if(visy[j])
						ly[j]+=d;
					else
						slack[j]-=d;
			}
	}
	int res=0;
	for(i=1;i<=ny;i++){
		if(link[i]>-1)
			res+=w[link[i]][i];
	}
	return res;
}
int main()
{
	int i,j;
	while(scanf("%d",&n)!=EOF){
		nx=ny=n;
		for(i=1;i<=nx;i++)
			for(j=1;j<=ny;j++)
				scanf("%d",&w[i][j]);
		printf("%d\n",KM());
	}
	return 0;
}