Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:1A

Posted by anyone_1 at 2010-10-06 00:26:57 on Problem 2195
In Reply To:1A Posted by:anyone_1 at 2010-10-06 00:26:08
```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 );
}
}
```

Followed by: