2195.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

/* * *			最小费用最大流			* * */

/*	notice:
	
	修改的dijstra + 双F算法		O( V^2 * M )	M为流量上限
	用于带权匹配 O( V^3 )
	  
*/

#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用来返回最大流量( 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)最短距离，用来修改边权的标记
	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( "%d\n", mf.min_fee_max_flow( h, 0, 1, 0 ) );
	}

	
	return 0;
}