KM竟然1A……n^3版
#include <stdio.h>
#include <string.h>
#define inf "home.in"
#define outf "home.out"
#define maxn 100 + 5
#define oo 2000000000
long A[ maxn ], B[ maxn ];
long slack[ maxn ];
long x[ maxn ], y[ maxn ];
long match[ maxn ];
long p[ maxn ][ maxn ];
long mx[ maxn ], my[ maxn ];
long hx[ maxn ], hy[ maxn ];
long n, m, M, H;
long ans = 0;
long abs ( long a )
{ if ( a < 0 ) a = -a; return ( -a ); }
int dfs ( long i )
{
	long j;
	if ( x[ i ] == 1 ) return ( 0 );
	x[ i ] = 1;
	for ( j = 1; j <= M; j++ )
		if ( A[ i ] + B[ j ] + p[ i ][ j ] == 0 )
			{
				if ( ! y[ j ] )
					{
						y[ j ] = 1;
						if ( ! match[ j ] || dfs ( match[ j ] ) )
							{
								match[ j ] = i;
								return ( 1 );
							}
					}
			} else
			if ( slack[ j ] > A[ i ] + B[ j ] + p[ i ] [ j ] )
				slack[ j ] = A[ i ] + B[ j ] + p[ i ] [ j ];
	return ( 0 );
}
void KM ()
{
	long i, j, d;
	memset ( B, 0, sizeof ( 0 ) );
	memset ( match, 0, sizeof ( match ) );
	for ( i = 1; i <= M; i++ )
		{
			A[ i ] = -oo;
			for ( j = 1; j <= H; j++ )
				if ( A[ i ] < -p[ i ][ j ] )
					A[ i ] = -p[ i ][ j ];
		}
	for ( i = 1; i <= M; i++ )
		while ( 1 )
			{
				memset ( x, 0, sizeof ( x ) );
				memset ( y, 0, sizeof ( y ) );
				for ( j = 1; j <= H; j++ ) slack[ j ] = oo;
				if ( dfs ( i ) ) break;
				d = oo;
				for ( j = 1; j <= H; j++ )
					if ( ( ! y[ j ] ) && d > slack[ j ] )
						d = slack[ j ];
				for ( j = 1; j <= M; j++ ) if ( x[ j ] ) A[ j ] -= d;
				for ( j = 1; j <= H; j++ ) if ( y[ j ] ) B[ j ] += d;
			}
	ans = 0;
	for ( i = 1; i <= H; i++ ) ans += p[ match[ i ] ][ i ];
	return;
}
int main ()
{
	long i, j;
	char s[ maxn ] = { 0 };
	while ( 1 )
		{
			scanf ( "%ld%ld\n", & n, & m );
			if ( n == 0 ) return ( 0 );
			M = H = 0;
			for ( i = 1; i <= n; i++ )
				{
					gets ( s );
					for ( j = 0; j < m; j++ )
						if ( s[ j ] == 'm' ) { M++; mx[ M ] = i; my[ M ] = j + 1; } else 
						if ( s[ j ] == 'H' ) { H++; hx[ H ] = i; hy[ H ] = j + 1; } 
				}
			for ( i = 1; i <= M; i++ )
				for ( j = 1; j <= H; j++ )
					p[ i ][ j ] = abs ( mx[ i ] - hx[ j ] ) + abs ( my[ i ] - hy[ j ] );
			KM ();
			printf ( "%ld\n", ans );
		}
}

• Re:1A (14) yy17yy 2010-12-04 15:57:08