Cod sursa(job #2402849)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 11 aprilie 2019 08:38:13
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <bits/stdc++.h>
#define pb push_back
#define sink ( n << 1 | 1 )
#define source sink + 1
using namespace std ;
const int NR = 205 ;
ifstream in ("harta.in") ;
ofstream out ("harta.out") ;
vector < int > v [ NR ] ;
int n , cap [ NR ][ NR ] , sol , father [ NR ] , init [ NR ][ NR ]  ;
bool edge [ NR ][ NR ] ;
bool bfs () {

    int nod , i , flow , pas ;
    queue < int > q ;
    vector < int > :: iterator it ;
    for ( i = 0 ; i <= source ; ++ i )    father [ i ] = 0 ;
    father [ source ] = -1 ;
    q.push ( source ) ;
    while ( !q.empty() )    {
        nod = q.front() ;
        q.pop() ;
        for ( it = v [ nod ].begin() ; it != v [ nod ].end() ; ++ it )
            if ( cap [ nod ][ *it ] && !father [ *it ] )    {
                father [ *it ] = nod ;
                q.push( *it ) ;
            }
    }
    if ( !father [ sink ] ) return 0 ;

    for ( it = v [ sink ].begin() ; it != v [ sink ].end() ; ++ it )  {

        nod = *it ;
        flow = cap [ *it ][ sink ] ;
        for ( ; nod != source && flow ; nod = father [ nod ] )
        flow = min ( flow , cap [ father [ nod ] ][ nod ] ) ;
        if ( !flow )    continue ;
        nod = *it ;
        cap [ *it ][ sink ] -= flow ;
        cap [ sink ][ *it ] += flow ;
        pas = 1 ;
       for ( ; nod != source ; nod = father [ nod ] , pas ++ ) {
        cap [ father [ nod ] ][ nod ] -= flow ;
        cap [ nod ][ father [ nod ] ] += flow ;
       }
       sol += flow ;
    }
    return 1 ;
}
int main () {
    int i , j , x , y ;
    in >> n ;
    for ( i = 1 ; i <= n ; ++ i )   {
        in >> x >> y ;
        cap [ source ][ i ] = x ;
        v [ i ].pb ( source ) ;
        v [ source ].pb ( i ) ;
        cap [ i + n ][ sink ] = y ;
        v [ i + n ].pb ( sink ) ;
        v [ sink ].pb ( i + n ) ;
    }
    for ( i = 1 ; i <= n ; ++ i )
    for ( j = 1 ; j <= n ; ++ j )   {
        if ( i == j )   continue ;
        cap [ i ][ n + j ] = 1 ;
        init [ i ][ n + j ] = 1 ;
        v [ i ].pb ( j + n ) ;
        v [ j + n ].pb ( i ) ;
    }
    while ( bfs() ) ;
    out << sol << '\n' ;
    for ( i = 1 ; i <= n ; ++ i )
    for ( j = 1 ; j <= n ; ++ j )
        if ( !cap [ i ][ j + n ] && init [ i ][ j + n ] )   out << i << ' ' << j << '\n' ;
}