http://poj.org/problem?id=2175
#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( "OPTIMALn" );
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( "SUBOPTIMALn" );
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;
}