Pagini recente » Cod sursa (job #1754815) | Cod sursa (job #2195680) | Cod sursa (job #2932394) | Cod sursa (job #2161728) | Cod sursa (job #2402849)
#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' ;
}