2391.txt

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

#include <vector>
#include <algorithm>
#include <memory.h>


#define min(a,b) (((a)<(b))?(a):(b))

using namespace std;

typedef int type;
const int size = 410;
const type max = 1e10;

struct edge
{
	int to;
	type c, f;
	int rev_i;
};

typedef vector<edge> set_edge; 


set_edge e[size];
bool sign[size];
bool full[size];
int n;

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

void 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 add_edge( edge &ee, type d )
{
	ee.f += d;
	e[ ee.to ][ ee.rev_i ].f -= d;
}

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

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

/////////////////////////////////////////////////////////////////////////////////

__int64 dis[200][200];
int in[200], hold[200];

int x[2000], y[2000], l[2000];

const __int64 biggest = ( (__int64) 1 << 60 );
pair< int, int > s[40000];


bool cmp( pair< int, int > a, pair< int, int > b )
{
	return dis[ a.first ][ a.second ] < dis[ b.first ][ b.second ];
}

int main()
{
	int i, j, ff, n, k, flow, cow, valume, nodenum;
	__int64 temp;


// input node
	scanf( "%d %d", &n, &ff );

	cow = 0; valume = 0;
	for( i=0; i<n; i++ )
	{
		scanf( "%d %d", &in[i], &hold[i] );
		cow += in[i];
		valume += hold[i];
	}

	if( cow > valume )
	{
		printf( "-1\n" );
		return 0;
		//continue;
	}

// input edge
	for( i=0; i<ff; i++ )
	{
		scanf( "%d %d %d", &x[i], &y[i], &l[i] );
		x[i]--, y[i]--;
	}

	
	for( i=0; i<n; i++ )
	for( j=0; j<n; j++ )
		dis[i][j] = ( i==j ? 0 : biggest );

	for( i=0; i<ff; i++ )
		if( dis[ x[i] ][ y[i] ] > l[i] )
			dis[ x[i] ][ y[i] ] = dis[ y[i] ][ x[i] ] = l[i];

// floyd
	for( k=0; k<n; k++ )
	for( i=0; i<n; i++ )
	for( j=i+1; j<n; j++ )
		if( ( temp = dis[i][k] + dis[k][j] ) < dis[i][j] )
			dis[j][i] = dis[i][j] = temp;

// insert_edge
	k = 0;
	nodenum = n*2+2;

	for( i=0; i<n; i++ )
	for( j=0; j<n; j++ )
		s[k++] = pair<int, int>( i, j );

	sort( s, s+k, cmp );
			
	clear();
	for( i=1; i<=n; i++ )
	{
		if( in[i-1] ) insert_edge( 0, i, in[i-1] );
		if( hold[i-1] ) insert_edge( i+n, nodenum-1, hold[i-1] );
	}

	bool key;
	flow = 0;
	for( i=0; i<n*n; i++ )
	{
		if( dis[ s[i].first ][ s[i].second ] == biggest )
			break;
		key = 0;

		while( i<n*n-1 && dis[ s[i].first ][ s[i].second ] == dis[ s[i+1].first ][ s[i+1].second ] )
		{
			if( hold[ s[i].second ] ) 
			{
				insert_edge( s[i].first+1, s[i].second+1+n, 999999 );
				if( !sign[ s[i].second+1+n ] && in[ s[i].first ] ) key = 1;
			}
			i++;

		}
		if( hold[ s[i].second ] )
		{
			insert_edge( s[i].first+1, s[i].second+1+n, 999999 );
			if( !sign[ s[i].second+1+n ] && in[ s[i].first ] ) key = 1;
		}
		
		if( key )
		{
			flow += maxflow( nodenum, 0, nodenum-1 );
			if( flow == cow ) break;
		}
	}

	if( flow == cow )printf( "%I64d\n", dis[ s[i].first ][ s[i].second ] );
	else printf( "-1\n" );


	return 0;
}