> //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;
> }

• 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