Pagini recente » Cod sursa (job #819438) | Cod sursa (job #574647) | Cod sursa (job #3179617) | Cod sursa (job #111683) | Cod sursa (job #189973)
Cod sursa(job #189973)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define FIN "harta.in"
#define FOUT "harta.out"
#define ABS( a ) (a) < 0 ? -(a) : (a)
#define NMAX 102
int C[NMAX][NMAX], F[NMAX][NMAX];
int SEL[NMAX], Q[NMAX], T[NMAX];
int N, S, D, flow = 0;
void BFS()
{
int p = 1, u = 1, nod, i;
memset( SEL, 0, sizeof(SEL));
Q[p] = S; T[S] = 0; SEL[S] = 1;
while( p <= u )
{
nod = Q[p];
for( i = S; i <= D; i++ )
if( !SEL[i] )
if( C[nod][i] - F[nod][i] > 0 )
Q[++u] = i, T[i] = nod, SEL[i] = 1;
else
if( F[i][nod] > 0 )
Q[++u] = i, T[i] = -nod, SEL[i] = 1;
p++;
}
}
void Relax( int x )
{
int d;
while( T[x] != 0 )
{
d = ABS(T[x]);
if( T[x] > 0 )
F[d][x]++;
else
F[x][d]--;
x = d;
}
}
void FLOW()
{
do
{
BFS();
if( SEL[D])
Relax(D), flow++;
}while(SEL[D]);
}
int main()
{
int i, j;
FILE * fin = fopen( FIN, "r" );
FILE * fout = fopen( FOUT, "w" );
fscanf( fin, "%d", &N );
S = 1; D = 2 * N + 2;
for( i = 1; i <= N; i++ )
fscanf( fin, "%d%d", &C[S][i+1], &C[i+N+1][D]);
for( i = 2; i <= N + 1; i++ )
for( j = N + 2; j <= 2 * N + 1; j++ )
if( j - i != N )
C[i][j] = 1;
FLOW();
fprintf( fout, "%d\n", flow );
for( i = 2; i <= N + 1; i++ )
for( j = N + 2; j < D; j++ )
if( F[i][j] )
fprintf( fout, "%d %d\n", i - 1, j - N - 1);
fclose( fin );
fclose( fout );
return 0;
}