2516.txt

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

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
typedef int type;
const type MAX_FEE = 1e8;
const int size = 210;
const int MAX = 1e8;
struct edge
{
	int c,f;
	type w;
	int from,to;
	int rev_i;
};
vector<edge> e[size];
type dis[size], fee, sum, rest;
bool sign[size];
edge *from[size];
int n, s, t;
int maxflow, add;
void clear()
{
	int i;
	for( i=0; i<n; i++ )
		e[i].clear();
	rest = 0;
}
bool dijstra( )
{
	int i, j, k, to, v;
	for( i=0; i<n; i++ )
		dis[i] = 999999;
	memset( sign, 0, sizeof(bool)*n );
	memset( from, 0, sizeof(edge * )*n );
	dis[ s ] = 0;
	for( i=0; i<n; i++ )
	{
		k = -1;
		for( j=0; j<n; j++ )
			if( !sign[j] && dis[j] < 999999 && ( k < 0 || dis[k] > dis[j] ) )
				k = j;
		if( k == -1 )
			break;
		sign[ k ] = true;
		for( j=0; j<e[k].size(); j++ )
		if( e[k][j].f != e[k][j].c )
		{	
			to = e[k][j].to;
			if( !sign[to] && e[k][j].f != e[k][j].c && dis[ to ] > ( v = dis[ k ] + e[k][j].w ) )
			{
				if( e[k][j].w < 0 )
					while( printf( "ft" ) );

				dis[ to ] = v;
				from[ to ] = &e[k][j];
			}
		}
	}
	return sign[t] == true;
}
void increse( edge *ep, int d )
{
	ep->f += d;
	e[ep->to][ep->rev_i].f -= d;
}
void modify( )
{
	int i, j, temp;
	add = MAX; sum = 0;
	for( i=t; i!=s; i = from[i]->from )
	{
		sum += from[i]->w;
		if( ( temp = from[i]->c - from[i]->f ) < add )
			add = temp;
	}
	sum += rest;
	rest += dis[t];
	
	for( i=t; i!=s; i = from[i]->from )
		increse( from[i], add );

	for( i=0; i<n; i++ )
	for( j=0; j<e[i].size(); j++ )
		e[i][j].w = dis[i] - dis[ e[i][j].to ] + e[i][j].w;

	return;
}
void insert_edge( int from, int to, int c, type w )
{
	edge eg1 = { c, 0, w, from, to, e[to].size() }, eg2 = { 0, 0, -w, to, from, e[from].size() };
	e[from].push_back( eg1 );
	e[to].push_back( eg2 );
}
type min_fee_max_flow( int nodenum, int begin, int end, int *flow )
{

	fee = 0; maxflow = 0;
	n = nodenum, s = begin, t = end;	
	while( dijstra( ) )
	{
		modify( );
		fee += sum*add;
		maxflow += add;
	}	
	if( flow )
		*flow = maxflow;

	return fee;
}
int shop[50][50];
int t_s[50], t_n[50];
int need[50][50];
int main()
{
	int n, m, k, i, j, l, f, ans;
	bool key;
	while( 1 )
	{
		scanf( "%d %d %d", &n, &m, &k );
		if( n == 0 ) break;
		for( i=0; i<k; i++ )
			t_s[i] = t_n[i] = 0;
		for( i=0; i<n; i++ )
		for( j=0; j<k; j++ )
		{
			scanf( "%d", &need[i][j] );
			t_n[j] += need[i][j];
		}
		for( i=0; i<m; i++ )
		for( j=0; j<k; j++ )
		{
			scanf( "%d", &shop[i][j] );
			t_s[j] += shop[i][j];
		}		
		for( i=0; i<k; i++ )
			if( t_s[i] < t_n[i] )
				break;
		if( i < k ) key = false;
		else key = true;
		ans = 0;
		for( l=0; l<k; l++ )
		{
			clear();
			if( key )
			{
				for( i=0; i<m; i++ )
				if( shop[i][l] )insert_edge( 0, i+2, shop[i][l], 0 );
		
				for( i=0; i<n; i++ )
				if( need[i][l] )insert_edge( i+2+m, 1, need[i][l], 0 );
			}
			for( i=0; i<n; i++ )
			for( j=0; j<m; j++ )
			{
				scanf( "%d", &f );
				if( key )
					insert_edge( j+2, i+2+m, 10000, f );
			}
			if( key )
				ans += min_fee_max_flow( n+m+2, 0, 1, 0 );
		}
		if( key )
			printf( "%d\n", ans );
		else
			printf( "-1\n" );
	}
	return 0;
}