1149.txt

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

/* * *    最大流	preflow-push ( lift-to front ) 算法	* * */

/*	notice:
	执行clear()删除所有的边。
	O( V^3 )
*/

#include <list>
#include <vector>

using namespace std;



class pre_f
{

public:

	enum{ MAX = 1000000000 };		//最大流上限
	enum{ size = 103 };				//图顶点规模(*)

	// 插入一条从 from 到 to 的 截量为 c 的边
	void insert_edge( int from, int to, int c );
	// 删除所有边
	void clear();
	//求节点数为nodenum (0...nodenum-1 ) 的最大流， begin 为源, end为汇								
	int maxflow( int nodenum, int begin, int end );

private:
	/* needn't care */

	struct edge
	{
		int to;
		int f, c;
		int rev_i;
	};//边的定义

	int h[size];	//高度
	int r[size];	//余流
	int cur[size];	//当前考虑的边指针

	vector<edge> e[size];	//邻接表
	list<int> l;		//顶点链表

	int n, s, t;		//顶点数，源， 汇

	void push( int a, edge &s );
	void lift( int a );
	void init();
	void dischange( int a );

};

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


void pre_f::insert_edge( int from, int to, int c )
{
	edge e1 = { to, 0, c, e[to].size() }, e2 = { from, 0, 0, e[from].size() };
	
	e[from].push_back( e1 );
	e[to].push_back( e2 );

}

void pre_f::clear()
{
	int i;
	for( i=0; i<size; i++ )
		e[i].clear();
	
	l.clear();
}

void pre_f::push( int a, edge &s )
{
	int y = s.c - s.f, x = r[a]<y?r[a]:y;
	s.f += x;
	e[ s.to ][ s.rev_i ].f = - s.f;
	r[a] -= x;
	r[s.to] += x;
}

void pre_f::lift( int a )
{
	int i, t = size*10;

	for( i=0; i<e[a].size(); i++ )
		if( e[a][i].f < e[a][i].c && t > h[ e[a][i].to ] )
			t = h[ e[a][i].to ];
	h[a] = t + 1;
}

void pre_f::init()
{
	int i;
	for( i=0; i<n; i++ )
		h[i] = 0, r[i] = 0;
	
	h[s] = n;
	r[s] = MAX;

	for( i=0; i<e[s].size(); i++ )
		push( s, e[s][i] );

	l.clear();

	for( i=0; i<n; i++ )
	{
		cur[i] = 0;
		if( i != s && i != t )
			l.push_back( i );
	}

}

void pre_f::dischange( int a )
{
	int k;

	while( r[a] )
	{
		k = cur[a];
		if( k == e[a].size() )
		{
			lift( a );
			cur[a] = 0;
		}
		else if( e[a][k].c > e[a][k].f && h[a] == h[ e[a][k].to ] + 1 )
			push( a, e[a][k] );
		else cur[a]++;
	}
}

int pre_f::maxflow( int nodenum, int begin, int end )
{
	int h_old;
	list<int>::iterator it;

	n = nodenum, s = begin, t = end;

	init();

	for( it=l.begin(); it != l.end(); it++ )
	{
		h_old = h[ *it ];
		dischange( *it );
		if( h_old < h[ *it ] )
		{
			l.push_front( *it );
			l.erase( it );
			it = l.begin();
		}
	}

	return MAX - r[s];
}


/***********************************************************/

#include <stdio.h>

int pig[1000];
int pre[1000];

#include <memory.h>
pre_f mf;
bool sign[102][102];

int main()
{
	int n, m, i, j, k, h;
	scanf( "%d %d", &m, &n );

	memset( sign, 0, sizeof(sign) );

	for( i=0; i<m; i++ )
	{
		scanf( "%d", &pig[i] );
		pre[i] = -1;
	}
	
	for( i=2; i<n+2; i++ )
	{
		scanf( "%d", &h );
		k = 0;
		while( h-- )
		{
			scanf( "%d", &j );
			j--;
			if( pre[j] < 0 )
			{
				k += pig[j];				
			}
			else if( !sign[pre[j]][i] )
			{
				mf.insert_edge( pre[j], i, 2000000 );
				sign[pre[j]][i] = true;
			}

			pre[j] = i;
		}

		if( k )
			mf.insert_edge( 0, i, k );

		scanf( "%d", &k );
		mf.insert_edge( i, 1, k );
	}

	printf( "%d", mf.maxflow( n+2, 0, 1 ) );

	return 0;

}