Cod sursa(job #1449851)

Utilizator xtreme77Patrick Sava xtreme77 Data 10 iunie 2015 19:47:12
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.92 kb
/**
 * Code by Patrick Sava
 * "Spiru Haret" National College of Bucharest
 **/

# include "fstream"
# include "cstring"
# include "vector"
# include "queue"
# include "bitset"
# include "algorithm"
# include "map"
# include "unordered_map"
# include "deque"
# include "string"
# include "iomanip"
# include "cmath"
# include "stack"
# include "cassert"

const char IN [ ] =  "harta.in" ;
const char OUT [ ] = "harta.out" ;
const int MAX = 500 ;

# define pb push_back
# define mp make_pair
# define FORN( a , b , c ) for ( int a = b ; a <= c ; ++ a )
# define FORNBACK( a , b , c ) for ( int a = b ; a >= c ; -- a )

using namespace std ;

ifstream cin ( IN ) ;
ofstream cout ( OUT ) ;

int cap [ MAX ] [ MAX ] , flux [ MAX ] [ MAX ] ;

vector < int > gr [ MAX ] ;
int n ;

bitset < MAX > viz ;

queue < int > Q ;

int tata [ MAX ] ;

vector < pair < int , int > > sol ;

inline int bfs ( )
{
    int D = n << 1 | 1 ;
    viz.reset ( ) ;
    viz [ 0 ] = 1 ;
    Q.push ( 0 ) ;

    while ( !Q.empty() )
    {
        int nod = Q.front ( ) ;
        Q.pop ( ) ;

        for ( auto x : gr [ nod ] )
        {
            if ( cap [ nod ] [ x ] == flux [ nod ] [ x ] or viz [ x ] ) continue ;

            viz [ x ] = 1 ;
            tata [ x ] = nod ;
            Q.push ( x ) ;
        }
    }

    return viz [ D ] ;
}

int main()
{
    cin >> n ;
    FORN ( i , 1 , n )
    {
        int x , y ;
        cin >> x >> y ;
        cap [ 0 ] [ i ] = x ;
        cap [ i + n ] [ 2 * n + 1 ] = y ;
        gr [ 0 ].pb ( i ) ;
        gr [ i ].pb ( 0 ) ;
        gr [ i + n ].pb ( 2 * n + 1 ) ;
        gr [ 2 * n + 1 ].pb ( i + n ) ;

        FORN ( j , 1 , n )
        {
            if ( j != i )
            {
                gr [ j + n ].pb ( i ) ;
                gr [ i ].pb ( j + n ) ;
                cap [ i ] [ j + n ] = 1 ;
            }
        }
    }

    for ( ; bfs ( ) ; )
    {
        for ( auto x : gr [ 2 * n + 1 ] )
        {
            if ( viz [ x ] == 0 ) continue ;
            if ( cap [ x ] [ 2 * n + 1 ] == flux [ x ] [ 2 * n + 1 ] ) continue ;

            int local = 1 << 30 ;

            tata [ 2 * n + 1 ] = x ;

            for ( int i = n << 1 | 1 ; i ; i = tata [ i ] )
                local = min ( local , cap [ tata [ i ] ] [ i ] - flux [ tata [ i ] ] [ i ] ) ;

            if ( local == 0 ) continue ;

            for ( int i = n << 1 | 1 ; i ; i = tata [ i ] )
            {
                flux [ tata [ i ] ] [ i ] += local ;
                flux [ i ] [ tata [ i ] ] -= local ;
            }
        }
    }


    FORN ( i , 1 , n )
    {
        for ( auto x : gr [ i ] )
            if ( flux [ i ] [ x ] and x )
                sol.pb ( { i , x - n } ) ;
    }

    cout << ( int )sol.size ( ) << '\n' ;

    for ( auto x : sol )
        cout << x.first << ' ' << x.second << '\n' ;


    return 0;
}