Pagini recente » Cod sursa (job #908926) | Cod sursa (job #2366641) | Cod sursa (job #2872745) | Cod sursa (job #234359) | Cod sursa (job #399035)
Cod sursa(job #399035)
#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;
}