Pagini recente » Cod sursa (job #1016274) | Cod sursa (job #2780524) | Cod sursa (job #2647090) | Cod sursa (job #1712811) | Cod sursa (job #182513)
Cod sursa(job #182513)
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define NX 210
int S, T, N, flow, cap[ NX ][ NX ], pi[ NX ];
queue< int > Q;
void cit() {
int i, j;
scanf( "%d", &N );
S = 0; T = 2*N + 1;
for( i = 1; i <= N; i++ )
scanf( "%d %d ", &cap[i+N][T], &cap[0][i] );
for( i = 1; i <= N; i++ )
for( j = 1; j <= N; j++ )
if( i != j )
cap[i][j+N] = 1;
N = T;
}
inline int MIN( int x, int y ) {
return x < y ? x : y;
}
void rez() {
int i, bot, u, v, z;
while( 1 ) {
memset( pi, -1, sizeof( pi ) );
pi[ S ] = -2;
while( !Q.empty() ) Q.pop();
Q.push( S );
while( !Q.empty() && pi[T] == -1 ) {
u = Q.front(), Q.pop();
for( i = 0; i <= N; i++ )
if( cap[u][i] && pi[i] == -1 )
pi[i] = u, Q.push( i );
}
if( pi[ T ] == -1 )
break;
for( z = 0; z <= N; z++ ) if( cap[z][T] && pi[z] != -1 ) {
bot = cap[z][T];
for( u = pi[z], v = z; u >= 0; v = u, u = pi[u] )
bot = MIN( bot, cap[u][v] );
if( bot <= 0 ) continue;
cap[z][T] -= bot;
cap[T][z] += bot;
for( u = pi[z], v = z; u >= 0; v = u, u = pi[u] )
cap[u][v] -= bot,
cap[v][u] += bot;
flow += bot;
}
}
}
void scr() {
int i, j;
printf( "%d\n", flow );
N >>= 1;
for( i = 1; i <= N; i++ )
for( j = 1; j <= N; j++ )
if( cap[i][ j+N ] == 0 && i!=j )
printf( "%d %d\n", i, j );
}
int main() {
freopen( "harta.in", "r", stdin );
freopen( "harta.out", "w", stdout );
cit();
rez();
scr();
return 0;
}