最小费用最大流，地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=2195
#include <stdio.h>

const int MAX = 3276700;

const int LEN = 205;

int house[LEN][2];
int hl;
int man[LEN][2];
int ml;

void init ()
{
    
    hl = ml = 0;
}

struct
{
    int c;
    int f;
    int weight;
}map[LEN][LEN];

int nearl[LEN][LEN];

void initm ( int n )
{

    for ( int i=0; i<n; i++ )
    {
        nearl[i][0] = 1;
        for ( int j=0; j<n; j++ )
        {
            map[i][j].c = map[i][j].f = map[i][j].weight = 0;
        }
    }
}

void add ( int a, int b, int c, int weight )
{

    if ( ! map[a][b].c && ! map[b][a].c )
    {
        nearl[a][ nearl[a][0]++ ] = b;
        nearl[b][ nearl[b][0]++ ] = a;
    }
    map[a][b].c += c;
    map[a][b].weight += weight;
}

int cost[LEN];
int road[LEN];

int ad ( int s, int t, int *mincost )
{

    int p = t;
    int min = MAX;

    while ( p != s )
    {
        if ( min > map[ road[p] ][p].c - map[ road[p] ][p].f )
        {
            min = map[ road[p] ][p].c - map[ road[p] ][p].f;
        }
        p = road[p];
    }

    p = t;
    while ( p != s )
    {
        map[ road[p] ][p].f += min;
        map[ p ][ road[p] ].f -= min;
        *mincost += min * map[ road[p] ][p].weight;
        p = road[p];
    }
    return min;
}

int mima ( int s, int t, int n, int *mincost )
{

    int maxflow = 0;
    *mincost = 0;
    do
    {
        road[t] = -1;
        cost[s] = 0;
        for ( int i=1; i<n; i++ )
        {
            cost[i] = MAX;
        }

        int flag = 1;
        while ( flag )
        {
            flag = 0;
            for ( int v=0; v < n; v++ )
            {
                for ( int u=1; u<nearl[v][0]; u++ )
                {
                    if ( map[ nearl[v][u] ][v].f < map[ nearl[v][u] ][v].c && cost[ nearl[v][u] ] < MAX )
                    {
                        if ( cost[v] > cost[ nearl[v][u] ] + map[ nearl[v][u] ][v].weight )
                        {
                            cost[v] = cost[ nearl[v][u] ] + map[ nearl[v][u] ][v].weight;
                            road[v] = nearl[v][u];
                            flag = 1;
                        }
                    }
                }
            }
        }
        if ( road[t] != -1 )
        {
            maxflow += ad ( s, t, mincost );
        }
    }while ( road[t] != -1 );

    return maxflow;
}

int abs ( int a )
{

    return a > 0 ? a : -a;
}

int main ()
{

    int n, m;

    while ( scanf ( "%d%d", &n, &m ) != EOF && ( n || m ) )
    {
        int i, j;
        char in[105];

        gets ( in );
        init ();
        for ( i=0; i<n; i++ )
        {
            scanf ( "%s", &in );
            for ( j=0; j<m; j++ )
            {
                if ( in[j] == 'H' )
                {
                    house[hl][0] = i;
                    house[hl][1] = j;
                    hl ++;
                    continue;
                }
                if ( in[j] == 'm' )
                {
                    man[ml][0] = i;
                    man[ml][1] = j;
                    ml ++;
                    continue;
                }

            }
        }

        initm ( ml+hl+2 );
        for ( i=0; i<ml; i++ )
        {
            add ( 0, i+1, 1, 0 );
            add ( +1, 0, 0, 0 );
        }
        for ( i=0; i<ml; i++ )
        {
            for ( j=0; j<hl; j++ )
            {
                int weight = abs ( man[i][0]-house[j][0] ) + abs ( man[i][1]-house[j][1] );
                add ( i+1, ml+1+j, 1, weight );
                add ( ml+1+j, i+1, 0, -weight );
            }
        }
        for ( j=0; j<hl; j++ )
        {
            add ( ml+1+j, ml+hl+1, 1, 0 );
            add ( ml+hl+1, ml+1+j, 0, 0 );
        }

        int mincost;

        mima ( 0, ml+hl+1, ml+hl+2, &mincost );

        printf ( "%d\n", mincost );
    }
    return 0;
}