2175.txt

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

#include <memory.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define y1 yy1

const int size = 210;
int dis[size][size], n, m;
int x1[100], y1[100], x2[100], y2[100];

int s2[100], lim2[100];
int f[100][100];

inline int distance( int i, int j )
{
	return abs( x1[i] - x2[j] ) + abs( y1[i] - y2[j] ) + 1;
}

void init( )
{
	int i, j, t;
	
	for( i=0; i<n; i++ )
		scanf( "%d %d %*d", &x1[i], &y1[i] );
	for( j=0; j<m; j++ )
		scanf( "%d %d %d", &x2[j], &y2[j], &lim2[j] );

	memset( dis, 0x01, sizeof dis );
	memset( s2, 0, sizeof s2 );

	for( i=0; i<n; i++ )
	for( j=0; j<m; j++ )
	{
		scanf( "%d", &f[i][j] );
		t = distance( i, j );

		if( f[i][j] > 0 )
		{
			s2[j] += f[i][j];
			dis[2+n+j][2+i] = -t;
		}

		dis[2+i][2+n+j] = t;
	}

	for( i=0; i<n; i++ )
		dis[0][i+2] = 0;

	for( j=0; j<m; j++ )
	{
		if( lim2[j] > s2[j] )
			dis[2+n+j][1] = 0;
		dis[1][2+n+j] = 0;
	}

}

int from[size];
bool sign[size];

void doit( )
{
	int i, j, k, h = n+m+2, t, l;
	bool key;

	sizeof( from, 0, sizeof from );

	for( k=0, key=false ; k<h && !key; k++ )
	{
		key = true;
		for( i=0; i<h; i++ )
		for( j=0; j<h; j++ )
		if( ( t = dis[0][i] + dis[i][j] ) < dis[0][j] )
		{
			dis[0][j] = t;
			from[j] = i;
			key = false;
			l = j;
		}
	}

	if( key )
		printf( "OPTIMAL\n" );
	else
	{
		memset( sign, 0, sizeof sign );
		
		for( k = l; !sign[k]; k = from[k] )
			sign[k]  = true;

		j = k;
		do
		{
			i = from[j];
			if( i > 1 && j > 1 )
			{
				if( i< 2+n )
					f[i-2][j-n-2]++;
				else
					f[j-2][i-n-2]--;
			}
			j = i;
		}while( j != k );

		printf( "SUBOPTIMAL\n" );
		for( i=0; i<n; i++ )
		for( j=0; j<m; j++ )
		{
			printf( "%d", f[i][j] );
			if( j < m-1 )
				printf( " " );
			else
				printf( "\n" );
		}

	}

	return ;
}

int main( )
{
	while( scanf( "%d %d", &n, &m ) == 2 )
	{
		init( );
		doit( );
	}

	return 0;
}