Cod sursa(job #399035)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 19 februarie 2010 19:37:54
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <algorithm>
#include <queue>
#include <bitset>
#include <vector>
using namespace std;

#define INF 0x3f3f3f3f
#define DIM 1<<8

int N, XXX;
int t[ DIM], g_ext[ DIM ], g_int[ DIM ], cap[ DIM ][ DIM ], flx[ DIM ][ DIM ];
bitset <DIM> f;
queue <int> q;
vector <int> v[ DIM ];

inline int bf() {

    int nod;
    vector <int> :: iterator it;

    f.reset();
    f[ 2*N+1 ] = 1;
    for( q.push( 2*N+1 ); !q.empty(); q.pop() )
        if( q.front() != 2*N+2 ) {

            nod = q.front();
            for( it = v[ nod ].begin(); it != v[ nod ].end(); ++it )
                if( cap[ nod ][ *it ] - flx[ nod ][ *it ] > 0 && !f[ *it ] ) {

                    f[ *it ] = 1;
                    t[ *it ] = nod;
                    q.push( *it );
                }
        }

    return f[ N+2 ];
}

int main() {

    freopen( "harta.in", "r", stdin );
    freopen( "harta.out", "w", stdout );

    int i, j, nod, fmin;
    vector <int> :: iterator it;

    scanf( "%d", &N );
    for( i = 1; i <= N; ++i )
        scanf( "%d %d", &g_ext[ i ], &g_int[ i ] );

    for( i = 1; i <= N; ++i ) {

        v[ 2*N+1 ].push_back( i );
        v[ i ].push_back( 2*N+1 );
        cap[ 2*N+1 ][ i ] = g_ext[ i ];
    }
    for( i = 1; i <= N; ++i )
        for( j = 1; j <= N; ++j )
            if( i != j ) {

                v[ i ].push_back( j+N );
                v[ j+N ].push_back( i );
                cap[ i ][ j+N ] = 1;
            }
    for( i = N+1; i <= 2*N; ++i ) {

        v[ i ].push_back( 2*N+2 );
        v[ 2*N+2 ].push_back( i );
        cap[ i ][ 2*N+2 ] = g_int[ i-N ];
    }
    while( bf() )
        for( it = v[ 2*N+2 ].begin(); it != v[ 2*N+2 ].end(); ++it )
            if( cap[ *it ][ 2*N+2 ] - flx[ *it ][ 2*N+2 ] > 0 && f[ *it ] ) {

                t[ 2*N+2 ] = *it;
                fmin = INF;
                for( nod = 2*N+2; t[ nod ]; nod = t[ nod ] )
                    fmin = min( fmin, cap[ t[ nod ] ][ nod ] - flx[ t[ nod ] ][ nod ] );
                if( fmin ) {

                    for( nod = 2*N+2; t[ nod ]; nod = t[ nod ] ) {

                        flx[ t[ nod ] ][ nod ] += fmin;
                        flx[ nod ][ t[ nod ] ] -= fmin;
                    }
                    XXX += fmin;
                }
            }

//    for( int i = 1; i <= 2*N; ++i ) {
//
//        for( int j = 1; j <= 2*N; ++j )
//            printf( "%d ", flx[ i ][ j ] );
//        printf( "\n" );
//    }

    printf( "%d\n", XXX );
    for( i = 1; i <= N; ++i )
        for( j = N+1; j <= 2*N; ++j )
            if( flx[ i ][ j ] > 0 )
                printf( "%d %d\n", i, j-N );

    return 0;
}