Poj Solution 2175

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