Poj Solution 2195

http://poj.org/problem?id=2195

#include <vector>

using namespace std;

typedef int type;                //��������

const int size = 210;            //ͼ�Ķ���ģ
const type MAX_FEE = 10000000;        //��������
const int MAX = 1000;            //�������

class minfee_flow
{

public:

    //ɾ�����б�
    void clear();
    //���һ���from��to ����Ϊc ��λ������Ϊw �ı�
    void insert_edge( int from, int to, int c, type w );
    
    //    ����С�����������ط���
    //    nodenum���� ( �����0,1...nodenum-1 )
    //    beginΪԴ��endΪ�㣬flow��4���������( NULL��ʾ������ )
    type min_fee_max_flow( int nodenum, int begin, int end, int *flow );


private:
    /*    needn't care */

    struct edge
    {
        int c,f;
        type w;
        int to;
        int rev_i;
    };                    //�ߵĶ���

    vector<edge> e[size];                    //�ڽӱ�
    
    type fee, sum, dis[size+1], l[size];    //�ܷ��ã����·���úͣ�(dijstra)��̾��룬��4�޸ı�Ȩ�ı��
    bool sign[size];                        //(dijstra)�Ƿ�ȷ�����·
    edge *from[size];                        //(dijstra)���·���У��õ�����
    int pri[size];                            //(dijstra)..�õ��ǰ��
    int n, s, t;                            //������Դ����
    int maxflow, add;                        //�����ÿ�ε�����

    bool dijstra( );                    //(dijstra)
    void increse( edge *ep, int d );    //����*ep�����d
    void modify( );                        //�޸�l,�������·���

};

///////////////////////////////////////////////////////////////////////
//    ����ʵ��

void minfee_flow::clear()
{
    int i;
    for( i=0; i<n; i++ )
        e[i].clear();
}

bool minfee_flow::dijstra( )
{
    int i, j, k, to, v;

    for( i=0; i<=n; i++ )
        dis[i] = MAX_FEE;

    memset( sign, 0, sizeof(bool)*n );

    dis[ s ] = 0;

    for( i=0; i<n; i++ )
    {
        k = n;
        for( j=0; j<n; j++ )
            if( !sign[j] && dis[k] > dis[j] )
                k = j;

        if( k == n )
            break;

        sign[ k ] = true;

        for( j=0; j<e[k].size(); j++ )
        if( e[k][j].f != e[k][j].c )
        {
            to = e[k][j].to;
            if( !sign[to] && dis[ to ] > ( v = dis[ k ] + l[k] - l[to] + e[k][j].w ) )
            {
                dis[ to ] = v;
                pri[ to ] = k;
                from[ to ] = &e[k][j];
            }
        }
    }

    return sign[t] == true;
}

void minfee_flow::increse( edge *ep, int d )
{
    ep->f += d;
    e[ep->to][ep->rev_i].f -= d;
}

void minfee_flow::modify( )
{
    int i, temp;

    add = MAX; sum = 0;
    for( i=t; i!=s; i = pri[i] )
    {
        sum += l[pri[i]] - l[i] + from[i]->w;
        if( ( temp = from[i]->c - from[i]->f ) < add )
            add = temp;
    }

    sum += l[t];

    for( i=t; i!=s; i = pri[i] )
        increse( from[i], add );

    for( i=0; i<n; i++ )
        l[i] += dis[i];

    return;
}

void minfee_flow::insert_edge( int from, int to, int c, type w )
{
    edge eg1 = { c, 0, w, to, e[to].size() }, eg2 = { 0, 0, -w, from, e[from].size() };
    e[from].push_back( eg1 );
    e[to].push_back( eg2 );
}

type minfee_flow::min_fee_max_flow( int nodenum, int begin, int end, int *flow )
{

    fee = 0; maxflow = 0;
    n = nodenum, s = begin, t = end;
    memset( l, 0, sizeof(type)*n );

    while( dijstra( ) )
    {
        modify( );
        fee += sum*add;
        maxflow += add;
    }
    
    if( flow )
        *flow = maxflow;

    return fee;
}

///////////////////////////////////////////////////////////////////////////////////////////

#include <math.h>
#include <stdio.h>

minfee_flow mf;
char map[110][110];

int main()
{
    int n, m, a, b, i, j, h;
    int x1[100], y1[100], x2[100], y2[100]; 

    while( 1 )
    {
        scanf( "%d %d", &n, &m );
        
        if( n == 0 && m == 0 )
            break;
        
        for( i=0; i<n; i++ )
            scanf( "%s", map[i] );
        
        a = 0, b = 0;
        for( i=0; i<n; i++ )
        for( j=0; j<m; j++ )
            if( map[i][j] == 'H' )
            {
                x1[a] = i, y1[a] = j;
                a++;
            }
            else if( map[i][j] == 'm' )
            {
                x2[b] = i, y2[b] = j;
                b++;
            }

        mf.clear( );

        h = a+b+2;
        for( i=0; i<a; i++ )
        for( j=0; j<b; j++ )
            mf.insert_edge( 2+i, 2+a+j, 1, abs( x1[i]-x2[j] ) + abs( y1[i]-y2[j] ) );

        for( i=0; i<a; i++ )
            mf.insert_edge( 0, 2+i, 1, 0 );
        for( i=0; i<b; i++ )
            mf.insert_edge( 2+a+i, 1, 1, 0 );

        printf( "%dn", mf.min_fee_max_flow( h, 0, 1, 0 ) );
    }

    
    return 0;
}