#include <stdio.h>
#include <string.h>
#define MAXN 110
#define inf 1000000000
#define _clr(x) memset(x,0xff,sizeof(int)*n)
#define abs(x) ((x)<0?(-(x)):(x))
#define fee(m,h) (abs(m.x-h.x)+abs(m.y-h.y))
typedef struct {
	int x,y;
}vex;
//模板开始
//#include <string.h>
//#define MAXN 110
//#define inf 1000000000
//#define _clr(x) memset(x,0xff,sizeof(int)*n)
//二分图最佳匹配,kuhn munkras算法,邻接阵形式,复杂度O(m*m*n)
//返回最佳匹配值,传入二分图大小m,n和邻接阵mat,表示权值
//match1,match2返回一个最佳匹配,未匹配顶点match值为-1
//一定注意m<=n,否则循环无法终止
//最小权匹配可将权值取相反数
int kuhn_munkras(int m,int n,int mat[][MAXN],int* match1,int* match2){
	int s[MAXN],t[MAXN],l1[MAXN],l2[MAXN],p,q,ret=0,i,j,k;
	for (i=0;i<m;i++)
		for (l1[i]=-inf,j=0;j<n;j++)
			l1[i]=mat[i][j]>l1[i]?mat[i][j]:l1[i];
	for (i=0;i<n;l2[i++]=0);
	for (_clr(match1),_clr(match2),i=0;i<m;i++){
		for (_clr(t),s[p=q=0]=i;p<=q&&match1[i]<0;p++)
			for (k=s[p],j=0;j<n&&match1[i]<0;j++)
				if (l1[k]+l2[j]==mat[k][j]&&t[j]<0){
					s[++q]=match2[j],t[j]=k;
					if (s[q]<0)
						for (p=j;p>=0;j=p)
							match2[j]=k=t[j],p=match1[k],match1[k]=j;
				}
		if (match1[i]<0){
			for (i--,p=inf,k=0;k<=q;k++)
				for (j=0;j<n;j++)
					if (t[j]<0&&l1[s[k]]+l2[j]-mat[s[k]][j]<p)
						p=l1[s[k]]+l2[j]-mat[s[k]][j];
			for (j=0;j<n;l2[j]+=t[j]<0?0:p,j++);
			for (k=0;k<=q;l1[s[k++]]-=p);
		}
	}
	for (i=0;i<m;i++)
		ret+=mat[i][match1[i]];
	return ret;
}
//模板结束

int main(int argc, char *argv[])
{
	int mat[MAXN][MAXN], mat1[MAXN],mat2[MAXN];
	int n, m, ans;
	char str[MAXN];
	vex home[MAXN],men[MAXN];
	while (scanf("%d%d\n",&n,&m)==2 && (n||m)){
		int p=0;
		int q=0;
		for(int i=0; i<n; i++){
			gets(str);
			for(int j=0; j<m; j++){
				if(str[j]=='H'){
					home[p].x=i;
					home[p].y=j;
					p++;
				}else if(str[j]=='m'){
					men[q].x=i;
					men[q].y=j;
					q++;
				}
			}
		}
		for(int i=0; i<q; i++)
			for(int j=0; j<p; j++)
				mat[i][j] = -fee(men[i], home[j]);//最小用负权
		ans = kuhn_munkras(q,p,mat,mat1,mat2);
		printf("%d\n",abs(ans));

	}
	return 0;
}


Memory: 376K  Time: 0MS 
一次AC，模板V5

• Re: 基本相似 模板，， (0) ACColor 2010-08-04 15:10:20