2711.txt

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

Problem Id:2711  User Id:fzk 
Memory:632K  Time:46MS
Language:C++  Result:Accepted

Source 

#include <vector>
#include <string.h>
#include <math.h>
#include <stdio.h>
#define min(a,b) (((a)<(b))?(a):(b))

using namespace std;

class ff
{

public:	
	typedef int type;			// 边权类型
	enum { size = 810 };		// 顶点规模
	enum { max = ( 1<<30 ) };	// 最大流量的上限

	//	初始化
	void init();

	//	插入一条从 from 到 to 的流量上限为 limit 的有向边
	void insert_edge( int from, int to, type limit );

	//	返回n个顶点的图中，从 顶点s 到 顶点t 的最大流
	type maxflow( int n, int s, int t );

private:

	struct edge
	{
		int to;		// 该边指向的顶
		type c, f;  // 截量，流函数
		int rev_i;  // e[to][rev_i] 为该边的逆向边
	};//边的类型

	typedef vector<edge> set_edge;  // 边的集合类型

	set_edge e[size]; // 边
	bool sign[size];  // 访问标志
	
	void add_flow( edge &ee, type d );		// 增加边的流量
	type search( int k, int t, int best );  // 搜索可增载轨并增载
};

/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
//	函数体


void ff::init()
{
	int i;
	for( i=0; i<size; i++ )
		e[i].clear();
}
void ff::insert_edge( int from, int to, type limit )
{
	edge e1 = { to, limit, 0, e[to].size() }, e2 = { from, 0, 0, e[from].size() };

	e[ from ].push_back( e1 );
	e[ to ].push_back( e2 );
}

void ff::add_flow( edge &ee, type d )
{
	ee.f += d;
	e[ ee.to ][ ee.rev_i ].f -= d;
}

ff::type ff::search( int k, int t, int best )
{
	int i, m = e[k].size();

	type temp;
	edge *ep;

	sign[k] = true;

	if( k == t )
		return best;

	for( i=0; i<m; i++ )
	{
		ep = &e[k][i];
		if( ep->f < ep->c && !sign[ ep->to ] )
		{
			if( ( temp = search( ep->to, t, min( best, ep->c - ep->f ) ) ) > 0 )
			{
				ep->f += temp;
				e[ ep->to ][ ep->rev_i ].f -= temp;
				return temp;
			}
		}
	}
	return 0;
}

ff::type ff::maxflow( int n, int s, int t )
{
	type total = 0, add = 0;

	do
	{
		total += add;
		memset( sign, 0, n );
	}
	while( ( add = search( s, t, max ) ) > 0 );

	return total;
}

/****************************************************************************/
char map[20][25];
char at[20][25];
int n, m, d, begin, end, total;
ff mf;

void init()
{
    int i, j, k, l;
    scanf( "%d %d", &n, &d );
    
    for( i=0; i<n; i++ )
    	scanf( "%s", map[i] );
	for( i=0; i<n; i++ )
		scanf( "%s", at[i] );
		
 	m = strlen( map[0] );
 	
 	mf.init();
 	
 	for( i=0; i<n; i++ )
 	for( j=0; j<m; j++ )
    	if( map[i][j] > '0' )
    		mf.insert_edge( i*m+j, i*m+j+n*m, map[i][j] -'0' );
	for( i=0; i<n; i++ )
	for( j=0; j<m; j++ )
	if( map[i][j] >'0' )
	for( k=(i-d>0)?i-d:0; k<=i+d&&k<n; k++ )
	for( l=(j-d>0)?j-d:0; l<=j+d&&l<m; l++ )
		if( map[k][l] > '0' && abs( i-k ) + abs( j-l ) <= d )
			mf.insert_edge( i*m+j+n*m, k*m+l, map[k][l] - '0' );

	begin = n*m*2;
	end = n*m*2+1;
	total = 0;
	
	for( i=0; i<n; i++ )
	for( j=0; j<m; j++ )
		if( at[i][j] == 'L' )
		{
      		mf.insert_edge( begin, i*m+j, 1 );
      		total++;
    	}  		
			
	for( i=0; i<n; i++ )
	for( j=0; j<m; j++ )
	if( map[i][j] > '0' )		
  		if( i-d<0 || i+d >= n || j-d<0 || j+d >= m )
			mf.insert_edge( i*m+j+n*m, end, map[i][j] - '0' );
}

int main()
{
    int cas, ans, i;
    
    scanf( "%d", &cas );
    
    for( i=1; i<=cas; i++ )
    {
        init();
        ans = total - mf.maxflow( n*m*2+2, begin, end );
        
        printf( "Case #%d: ", i );
        
        if( ans == 0 )
        	printf( "no lizard was left behind.\n" );
    	else if( ans == 1 )
    		printf( "1 lizard was left behind.\n" );
		else
  			printf( "%d lizards were left behind.\n", ans );
 	} 			
	return 0;
}