Cod sursa(job #143823)

Utilizator mithyPopovici Adrian mithy Data 26 februarie 2008 21:33:30
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <stdio.h>
#define NMax 101

int n, nr;
int intrare[NMax], iesire[NMax];
int flux[NMax][NMax], C[NMax*2], prec[NMax*2], fin[NMax], fout[NMax], in, sf;

void citire();
void rez();
void afis();

int main()
{
	citire();
	rez();
	afis();
	return 0;
}
void afis()
{
	int i, j;

	printf( "%d\n", nr - 1);

	for (i=1; i<=n; i++)
		for (j=n+1; j<=n*2; j++)
			if ( flux[i][j-n] )
				printf( "%d %d\n", i, j-n );
}
void rez()
{
	int i, j, aux;

	while ( 1 )
	{
		nr++;
		in = sf = 0;

		// bfs din sursa
		for (i=1; i<=n; i++)
		{
			prec[i] = prec[i+n] = -1;
			if ( fin[i] < iesire[i] )
			{
				prec[i] = 0;
				C[sf++] = i;
			}
		}

		// bfs din noduri 1..2n
		while ( in <= sf )
		{	
			aux = C[in++];

			// stanga
			if ( aux <= n )
			{
				for (i=n+1; i<=n*2; i++)
					if ( !flux[aux][i-n] && aux != i-n && prec[i] == -1 )
					{
						C[sf++] = i;
						prec[i] = aux;
					}
			}
			// dreapta
			else
			{
				for (i=1; i<=n; i++ )
					if ( flux[i][aux-n] && i != aux-n && prec[i] == -1 )
					{
						C[sf++] = i;
						prec[i] = aux;
					}
			}		
		}	

		aux = 0;
		// bfs spre destinatie
		for (i=n+1; i<=n*2; i++)
			if ( prec[i] != -1 && fout[i-n] < intrare[i-n] )
			{
				aux = i;
				break;
			}
		
		if ( aux == 0 )
			break;

		fout[aux - n]++;
		while ( prec[aux] != 0 )
		{
			if ( aux <= n )
				flux[aux][prec[aux]-n]--;
			else
				flux[prec[aux]][aux-n]++;

			aux = prec[aux];
		}
		fin[aux]++;
	}

}
void citire()
{
	int i;
	freopen( "harta.in", "rt", stdin );
	freopen( "harta.out", "wt", stdout );

	scanf( "%d", &n );
	for (i=1; i<=n; i++)
		scanf( "%d %d", &iesire[i], &intrare[i]);
}