//lx ly 是顶标，这个去看看书吧。KM算法里的。
#include <iostream>
using namespace std;
#define MAXN 101
int n,m,x[MAXN][2],y[MAXN][2],lx[MAXN],ly[MAXN],g[MAXN][MAXN],xi,yi;
char map[MAXN][MAXN];
int marka[MAXN],markb[MAXN];
int mb[MAXN];
int total,al;

int find(int x){
	int j;
	marka[x]=1;
	for(j=1;j<=yi;j++)
		if(!markb[j] && (lx[x]+ly[j]==g[x][j])){
			markb[j]=1;
			if(!mb[j] || find(mb[j])){
				mb[j]=x;
				return 1;
			}
		}
	return 0;
}

int main(){
	int i,j,k;
	while(cin>>n>>m,!(n==0 && m==0)){
		memset(x,0,sizeof(x));
		memset(y,0,sizeof(y));
		memset(ly,0,sizeof(ly));
		memset(g,0,sizeof(g));
		memset(mb,0,sizeof(mb));
		memset(map,0,sizeof(map));
		xi=yi=total=0;
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++){
				cin>>map[i][j];
				if(map[i][j]=='m') {xi++; x[xi][0]=i; x[xi][1]=j;}
				if(map[i][j]=='H') {yi++; y[yi][0]=i; y[yi][1]=j;}
			}
		for(i=1;i<=xi;i++)
			lx[i]=0x80000000;
		for(i=1;i<=xi;i++)
			for(j=1;j<=yi;j++){
				g[i][j]=-(abs(x[i][0]-y[j][0])+abs(x[i][1]-y[j][1]));
				if(lx[i]<g[i][j]) lx[i]=g[i][j];
			}
		for(i=1;i<=xi;i++){
			while(1){
				memset(marka,0,sizeof(marka));
				memset(markb,0,sizeof(markb));
				if(find(i)) break;
				al=0x7fffffff;
				for(j=1;j<=xi;j++)
					if(marka[j])
						for(k=1;k<=yi;k++)
							if(!markb[k])
								if(al>lx[j]+ly[k]-g[j][k])
									al=lx[j]+ly[k]-g[j][k];

				for(j=1;j<=xi;j++) if(marka[j]) lx[j]-=al;
				for(j=1;j<=yi;j++) if(markb[j]) ly[j]+=al;
			}
		}
		total=0;
		for(i=1;i<=yi;i++)
			total+=g[mb[i]][i];
		cout<<-total<<endl;
	}


return 0;
}

• g[i][j]=-(abs(x[i][0]-y[j][0])+abs(x[i][1]-y[j][1])); 为什么加 － 号 (1747) swust20064469 2008-10-22 17:06:47
  • if a>b >=0 then -a<-b (4) kamel52045386 2008-10-22 17:13:54
  • Re:g[i][j]=-(abs(x[i][0]-y[j][0])+abs(x[i][1]-y[j][1])); 为什么加 － 号 (35) yzy123 2010-03-18 11:11:10
• Re:贴个自己的AC的程序，0MS，但内存用了不少，其实很好改进。用模板做累死了，还是自己想。 (18) tiye125 2010-03-18 19:09:36