Pagini recente » Cod sursa (job #3211819) | Cod sursa (job #2676978) | Cod sursa (job #3265925) | Cod sursa (job #695545) | Cod sursa (job #719260)
Cod sursa(job #719260)
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define NMAX 210
#define INF 0x3f3f3f3f
#define pb push_back
int N, gin, gout, i, j, Nod, FluxCt, Flux, S, D;
int C[NMAX][NMAX], F[NMAX][NMAX], T[NMAX];
vector< int > G[NMAX];
bool Used[NMAX];
inline bool BF()
{
memset( T, 0, sizeof(T) );
queue< int > Q;
Q.push( S );
memset( Used, 0, sizeof(Used) );
Used[S] = true;
while( !Q.empty() )
{
Nod = Q.front();
Q.pop();
for( vector< int >::iterator it = G[Nod].begin(); it != G[Nod].end(); ++it )
if( !Used[*it] && C[Nod][*it] > F[Nod][*it] )
{
Used[*it] = true;
T[*it] = Nod;
Q.push( *it );
}
}
return Used[D];
}
int main()
{
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
memset( C, 0, sizeof(C) );
memset( F, 0, sizeof(F) );
scanf("%d", &N );
S = 0, D = 2*N + 1;
for( i = 1; i <= N; ++i )
{
scanf("%d%d", &gin, &gout );
G[S].pb( i );
G[i].pb( S );
G[D].pb( i + N );
G[i + N].pb( D );
C[S][i] = gin;
C[i + N][D] = gout;
}
for( i = 1; i <= N; ++i )
for( j = 1; j <= N; ++j )
if( i != j )
{
G[i].pb( j + N );
G[j + N].pb( i );
C[i][j + N] = 1;
}
for( Flux = 0; BF(); )
for( vector< int >::iterator it = G[D].begin(); it != G[D].end(); ++it )
if( Used[*it] && F[*it][D] < C[*it][D] )
{
T[D] = *it;
FluxCt = INF;
for( Nod = D; Nod != S; Nod = T[Nod] )
FluxCt = min( FluxCt, C[ T[Nod] ][Nod] - F[ T[Nod] ][Nod] );
if( !FluxCt ) continue;
for( Nod = D; Nod != S; Nod = T[Nod] )
F[ T[Nod] ][Nod] += FluxCt, F[Nod][ T[Nod] ] -= FluxCt;
Flux += FluxCt;
}
printf("%d\n", Flux );
for( i = 1; i <= N; ++i )
for( j = 1; j <= N; ++j )
if( F[i][j + N] )
printf("%d %d\n", i, j );
return 0;
}