hdu 2255二分圖最大權值匹配的KM 算法

我的理解：如有錯誤，請大牛指正！！

1.KM（）算法實際就是一種遍歷，從權值最大的開始匹配，如果成功的完備匹配了，那這個權值一定是最大的權值。因為我們是從最大的開始一點點小下來遍歷的。

2.slack[ ] 這個數組 可以說是一個 松弛變量數組 ，目的是為了 增加匹配。

3.實際也沒什麼好講的就是不斷的增廣，很多也都這樣，松弛迫近，跟那什麼單純形法有想通之處。

4. 匈牙利算法進行匹配的尋找。

hdu 2255

#include
#include
#include
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]-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
,KM());
	}
	return 0;
}