#include <iostream.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#define MAXN 105
#define INF 32767
int g[MAXN][MAXN],gt[MAXN][MAXN];
int l[2*MAXN];
int s[MAXN],t[MAXN],cx[MAXN],cy[MAXN];
int n,m;

int path(int x)
{
	int i,j,ret=0;
	for(i=1;i<=m;i++){
		if (!t[i]&&g[x][i]){
			t[i]=1;
			if (!cy[i]){
				g[x][i]=-g[x][i];cy[i]=1;
				ret=1;
				return ret;
			}
			j=1;
			while(j<=n&&!s[j]&&g[j][i]>=0) j++;
			if (j<=n){
				s[j]=1;
				if (path(j)){
					g[x][i]=-g[x][i];g[j][i]=-g[j][i];
					ret=1;
					return ret;
				}
			}
		}
	}
	return ret;
}
int kuhn_munkras()
{
	int u,i,j,al,edge;
	u=1;
	memset(l,0,sizeof(l));
	memset(cx,0,sizeof(cx));
	memset(cy,0,sizeof(cy));
	for(i=1;i<=n;i++)for(j=1;j<=m;j++){
		gt[i][j]=g[i][j];
		if (g[i][j]>l[i]) l[i]=g[i][j];
	}
	for(i=1;i<=n;i++)for(j=1;j<=m;j++){
		if (l[i]+l[n+j]==gt[i][j])g[i][j]=1;
		else g[i][j]=0;
	}
	while(u<=m){
		
		if (!cx[u]){
			memset(s,0,sizeof(s));
			memset(t,0,sizeof(t));
			s[u]=1;
			if (!path(u)){
				al=INF;
				for(i=1;i<=n;i++)for(j=1;j<=m;j++){
					
					if (s[i]&&!t[j]&&l[i]+l[n+j]-gt[i][j]<al){
						al=l[i]+l[n+j]-gt[i][j];
						
					}
				}
	
				for(i=1;i<=n;i++)if (s[i])l[i]=l[i]-al;
				for(i=1;i<=m;i++)if (t[i])l[n+i]=l[n+i]+al;
				edge=0;
				for(i=1;i<=n;i++)for(j=1;j<=m;j++){
					if (l[i]+l[n+j]==gt[i][j]){g[i][j]=1;edge++;}
					else g[i][j]=0;
				}
				memset(cx,0,sizeof(cx));
				memset(cy,0,sizeof(cy));
			}
			else cx[u]=1;
			u=0;
		}
		u++;
	}
	return 0;
}
int main()
{
	int r,c,i,j,k1,k2,tot;
	int M[MAXN][2],H[MAXN][2];
	char ch;
	freopen("e.in","r",stdin);
	while(cin>>r>>c){
		if (!r&&!c) break;
		
		k1=1;k2=1;
		for(i=0;i<r;i++){
			for(j=0;j<c;j++){
				cin>>ch;
				if (ch=='m'){M[k1][0]=i;M[k1++][1]=j;}
				if (ch=='H'){H[k2][0]=i;H[k2++][1]=j;}
			}
		}
		n=k1-1;
		m=k2-1;
		for(i=1;i<=n;i++)for(j=1;j<=m;j++){
			g[i][j]=abs(M[i][0]-H[j][0])+abs(M[i][1]-H[j][1]);
			g[i][j]=1000-g[i][j];
		}
		kuhn_munkras();
		tot=0;
		for(i=1;i<=n;i++)for(j=1;j<=m;j++){
			if (g[i][j]<0) tot+=gt[i][j];
		}
		cout<<1000*n-tot<<endl;
	}
	return 0;
}

• Re:这个程序怎么会陷入死循环? (41) xemoaya 2005-08-23 21:50:49
  • Re:这个程序怎么会陷入死循环? (92) jinmingyan 2005-08-24 19:43:47