Pagini recente » Cod sursa (job #231772) | Cod sursa (job #424898) | Cod sursa (job #2879) | Cod sursa (job #2153997) | Cod sursa (job #141524)
Cod sursa(job #141524)
#include <stdio.h>
#include <string.h>
#define FIN "harta.in"
#define FOUT "harta.out"
#define NMAX 210
#define ABS( a ) ( (a) < 0 ) ? - a : a
int gext[NMAX], gint[NMAX], FLOW[NMAX][NMAX], CAP[NMAX][NMAX];
int SEL[NMAX], Q[NMAX], T[NMAX];
int N, i, j, sursa, dest, flow = 0;
FILE * fin, * fout;
void BFS( int start )
{
int p, u, nod;
memset( SEL, 0, sizeof(SEL) );
memset( T, 0, sizeof(T) );
p = 1; u = 1; Q[p] = start; T[start] = - 1; SEL[start] = 1;
while ( ( p <= u ) && (!SEL[dest] ) )
{
nod = Q[p];
for ( i = sursa; i <= dest; i++ )
if (!SEL[i])
if ( CAP[nod][i] - FLOW[nod][i] > 0 )
{
T[i] = nod; u++; Q[u] = i; SEL[i] = 1;
}else
if (FLOW[i][nod] > 0 )
{
T[i] = - nod; u++; Q[u] = i; SEL[i] = 1;
}
p++;
}
}
void RELAX( int xp )
{
int tata;
while (T[xp] != -1 )
{
tata = ABS( T[xp] );
if ( T[xp] > 0 ) FLOW[tata][xp]++; else FLOW[xp][tata]--;
xp = tata;
}
}
int main()
{
fin = fopen( FIN, "r" );
fout = fopen( FOUT, "w" );
fscanf( fin, "%d\n", &N );
for( i = 1; i <= N; i++ ) fscanf( fin, "%d %d\n", &gext[i], &gint[i] );
sursa = 1; dest = 2 * N + 2;
memset( CAP, 0, sizeof(CAP) );
memset( FLOW, 0, sizeof(FLOW) );
for( i = 2; i <= N + 1; i++ ) CAP[sursa][i] = gext[i-1];
for( i = N + 2; i < dest; i++) CAP[i][dest] = gint[i-N-1];
for( i = 2; i <= N + 1; i++)
for( j = N + 2; j < dest; j++ ) CAP[i][j] = 1;
for( i = 2; i <= N + 1; i++ ) CAP[i][i+N] = 0;
flow = 0;
do
{
BFS(sursa);
if (SEL[dest])
{
flow++;
RELAX(dest);
}
}while(SEL[dest]);
fprintf( fout, "%d\n", flow );
for( i = 2; i <= N + 1; i++)
for( j = N + 2; j < dest; j++)
if (FLOW[i][j]) fprintf( fout, "%d %d\n", i - 1, j - N - 1 );
fclose(fin);
fclose(fout);
return 0;
}