# 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;                            //������Դ����

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 )
}

sum += l[t];

for( i=t; i!=s; i = pri[i] )

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( );
}

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;
}

```
This entry was posted in poj. Bookmark the permalink.