3189.txt

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

Source

Problem Id:3189  User Id:fzk 
Memory:9660K  Time:748MS
Language:C++  Result:Accepted

Source 

/////////////////////////////////////////////////////////////////////////////
/* * *    最大流	double F 算法	* * */

/*	notice:
	在执行init()前，流函数f不会自动初始化，即可在增加一条边后,在原来最大流的基础上执行maxflow
*/

#include <vector>
#define min(a,b) (((a)<(b))?(a):(b))

using namespace std;

class ff
{

public:	
	typedef int type;			// 边权类型
	enum { size = 1110 };		// 顶点规模
	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;
}


ff maxf[20];
int n, b;
int fav[1000][20];
int limit[20];

void input( ) {
	int i, j;
	scanf( "%d%d", &n, &b );
	for( i=0; i<n; i++ ) {
		for( j=0; j<b; j++ )
			scanf( "%d", &fav[i][j] );
	}
	for( i=0; i<b; i++ )
		scanf( "%d", &limit[i] );
}

void create( ff &maxf ) {
	int i;
	maxf.init( );
	for( i=0; i<n; i++ )
		maxf.insert_edge( 0, i+1, 1 );
	for( i=0; i<b; i++ )
		maxf.insert_edge( n+i+1, n+b+1, limit[i] );
}

int main( ) {
	int res[20], i, j, k;

	input( );

	for( i=0; i<b; i++ ) {
		create( maxf[i] );
		res[i] = 0;
	}

	for( i=0; i<b-1; i++ ) {
		for( j=0; j<b-i; j++ ) {
			for( k=0; k<n; k++ )
				maxf[j].insert_edge( k+1, n+fav[k][j+i], 1 );
			res[j] += maxf[j].maxflow( n+b+2, 0, n+b+1 );
			if( res[j] == n )
				goto end;
		}
	}
end:
	printf( "%d\n", i+1 );
	return 0;
}