我在三个小时前(18点)恢复网络,自我断网结束,比计划早了两个小时,因为我们几个ACM讨论需要。

今晚讨论的是带权的二分匹配问题,证明没看懂,只是会用了,模板就这个而已:

const int maxn=20,INF=2147483647;
int w[maxn][maxn];
int lx[maxn]={0},ly[maxn]={0}; //顶标
int linky[maxn];
int visx[maxn],visy[maxn];
int lack;
bool find(int x){
	visx[x]=true;
	for(int y=0;y<maxn; y++){
		if(visy[y])continue;
		int t=lx[x]+ly[y]-w[x][y];
		if(t==0){
			visy[y]=true;
			if(linky[y]==-1||find(linky[y])){
				linky[y]=x;
				return true;
			}
		}
		else if(lack>t)lack=t;
	}
	return false;
}
void KM(){
	memset(linky,-1,sizeof(linky));
	for(int i=0;i<maxn; i++)
		for(int j=0;j<maxn; j++)
			if(w[i][j]>lx[i])
				lx[i]=w[i][j]; //初始化顶标
	for(int x=0;x<maxn; x++){
		for(;;){
			memset(visx,0,sizeof(visx));
			memset(visy,0,sizeof(visy));
			lack=INF;
			if(find(x))break;
			for(int i=0;i<maxn; i++){
				if(visx[i])lx[i]-=lack;
				if(visy[i])ly[i]+=lack;
			}
		}
	}
}

修改一下,变成了poj 2195,就是最大匹配变成最小匹配,如下:

#include <stdio.h>
#include <string.h>

int House[105][2],Hc,Man[105][2],Mc;
const int maxn=200,INF=2147483647;
int w[maxn][maxn];
int lx[maxn]={0},ly[maxn]={0}; //顶标
int linky[maxn];
int visx[maxn],visy[maxn];
int lack;
bool find(int x){
	visx[x]=true;
	for(int y=0;y<Mc; y++){
		if(visy[y])continue;
		int t=w[x][y]-lx[x]-ly[y];
		if(t==0){
			visy[y]=true;
			if(linky[y]==-1||find(linky[y])){
				linky[y]=x;
				return true;
			}
		}
		else if(lack>t)lack=t;
	}
	return false;
}
void KM(){
	memset(linky,-1,sizeof(linky));
	for(int i=0;i<Mc; i++){
		ly[i]=0;
		lx[i]=INF;
		for(int j=0;j<Mc; j++)
			if(w[i][j]<lx[i])
				lx[i]=w[i][j]; //初始化顶标
	}
	for(int x=0;x<Mc; x++){
		for(;;){
			memset(visx,0,sizeof(visx));
			memset(visy,0,sizeof(visy));
			lack=INF;
			if(find(x))break;
			for(int i=0;i<Mc; i++){
				if(visx[i])lx[i]+=lack;
				if(visy[i])ly[i]-=lack;
			//	printf("%d %d %dn",lx[i],ly[i],lack);
			}
		}
	}
}

int abs(int x){
	if(x<0)return -x;
	return x;
}

int main(){
	int i,j,n,m,ans;
	char tmp;
	while(scanf("%d%d",&n,&m),n+m!=0){
		getchar();
		Hc=Mc=0;
		for(i=0;i<n;i++){
			for(j=0;j<m;j++){
				tmp=getchar();
				if(tmp=='H'){
					House[Hc][0]=i;
					House[Hc][1]=j;
					Hc++;
				}else if(tmp=='m'){
					Man[Mc][0]=i;
					Man[Mc][1]=j;
					Mc++;
				}
			}
			getchar();
		}
		for(i=0;i<Hc;i++){
			for(j=0;j<Mc;j++){
				w[j][i]=abs(House[i][0]-Man[j][0])+abs(House[i][1]-Man[j][1]);
			}
		}
		KM();
		ans=0;
		for(i=0;i<Mc;i++){
			ans+=lx[i];
			ans+=ly[i];
		}
		printf("%dn",ans);
	}
	return 0;
}