3068.txt

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

Source

Problem Id:3068  User Id:fzk 
Memory:72K  Time:0MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <memory.h>
#include <math.h>
#include <algorithm>
using namespace std;

#include <vector>

using namespace std;

typedef int type;				//费用类型

const int size = 230;			//图的顶规模
const type MAX_FEE = (1<<30);		//费用上限
const int MAX = (1<<30);			//流的上限
const int MAX_SIZE = size*size*2;

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;
		edge* rev;
		edge* next;
	};					//边的定义

	edge* e[size];					//邻接表
	static edge edge_cache[MAX_SIZE];
	static int en;

	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,计算最短路相关

};

///////////////////////////////////////////////////////////////////////
//	函数实现

int minfee_flow::en = 0;
minfee_flow::edge minfee_flow::edge_cache[MAX_SIZE];
///////////////////////////////////////////////////////////////////////
//	函数实现

void minfee_flow::clear()
{
	int i;
	for( i=0; i<n; i++ )
		e[i] = 0;
	en = 0;
}

bool minfee_flow::dijstra( )
{
	int i, j, k, to, v;
	edge *p;

	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( p=e[k]; p != NULL ; p = p->next )
		if( p->f != p->c )
		{
			to = p->to;
			if( !sign[to] && dis[ to ] > ( v = dis[ k ] + l[k] - l[to] + p->w ) )
			{
				dis[ to ] = v;
				pri[ to ] = k;
				from[ to ] = p;
			}
		}
	}

	return sign[t] == true;
}

void minfee_flow::increse( edge *ep, int d )
{
	ep->f += d;
	ep->rev->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, edge_cache+en+1, e[from] }, 
		 eg2 = { 0, 0, -w, from, edge_cache+en, e[to] };
	edge_cache[en] = eg1;
	edge_cache[en+1] = eg2;

	e[from] = edge_cache+en;
	e[to] = edge_cache+en+1;

	en += 2;
}

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

minfee_flow mf;

int main( ) {
	int n, m, a, b, v, i, ans, t = 0, fee;
	while( 1 ) {
		scanf( "%d%d", &n, &m );
		if( n == 0 && m == 0 )
			break;
		mf.clear( );
		
		for( i=0; i<m; i++ ) {
			scanf( "%d%d%d", &a, &b, &v );
			mf.insert_edge( a, b+n, 1, v );
		}

		for( i=1; i<n; i++ )
			mf.insert_edge( i+n, i, 1, 0 );
		mf.insert_edge( n, 0, 2, 0 );

		fee = mf.min_fee_max_flow( n*2, n, n*2-1, &ans );
		printf( "Instance #%d: ", ++t );

		if( ans < 2 )
			printf( "Not possible\n" );
		else
			printf( "%d\n", fee );
	}
	return 0;
}