Cod sursa(job #121186)

Utilizator Binary_FireFlorin Pg Binary_Fire Data 7 ianuarie 2008 22:36:28
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <cstdio>

#define fin  "harta.in"
#define fout "harta.out"

#define DxBG
#define FL

const int Nmax = 250;

int N,M,S,D;

int G[Nmax][Nmax],C[Nmax][Nmax],F[Nmax][Nmax];
int gradi[Nmax],grade[Nmax];

int q[Nmax],tat[Nmax];
int st,dr;

void readdata()
{
	int i;

	freopen(fin,"r",stdin);

	scanf("%d",&N);

	for (i=1;i<=N;++i)
		scanf("%d%d",&grade[i],&gradi[i]);
}

void init()
{
	int i,j;
	
	S = 2*N + 1;
	D = 2*N + 2;

	//initializez capacitatile de la sursa la noduri
	for (i=1;i<=N;++i)
	{
		C[S][i] = grade[i];
		G[S][i] = G[i][S] = 1;
	}

	//initializez capacitatile de la noduri' la destinatie
	for (i=1;i<=N;++i)
	{
		C[N+i][D] = gradi[i];
		G[N+i][D] = G[D][N+i] = 1;
	}

	//pun capacitate 1 de la fiecare nod la fiecare nod'
	for (i=1;i<=N;++i)
	for (j=1;j<=N;++j)
	if (i!=j)
	{
		C[i][N+j] = 1;
		G[i][N+j] = G[N+j][i] = 1;
	}
}

void bfs()
{
	int i,x,j,old;

	old=dr;

	for (i=st;i<=old;++i)
	{
		x=q[i];
		for (j=1;j<=2*N+2;++j)
			if (G[x][j] && tat[j]==-1 && F[x][j] < C[x][j])
			{
				++dr;
				q[dr]=j;
				tat[j]=x;
			}
	}

	st=old+1;

	if (st<=dr && tat[D]==-1) bfs();
}

void flux()
{
	int i,nod,flag=1;

	init();

	while (flag)
	{
		for (i=1;i<=2*N+2;++i)
			tat[i]=-1;

		st=dr=1;
		q[1]=S;
		tat[S]=0;

		bfs();
		
		flag=1;

		if ( tat[D] == -1 )
			flag=0;
		else
		{
			//fluxul de adaugat va fi intotdeauna 1
			nod=D;
			while (nod!=S)
			{
#ifdef DBG
				printf("%d ",nod);
#endif	
				++F[tat[nod]][nod];
				--F[nod][tat[nod]];
				nod=tat[nod];
			}
#ifdef DBG
			printf("\n");
#endif
		}
	}

	for (i=1;i<=N;++i)
		M+=F[N+i][D];
}

void printdata()
{
	int i,j;

#ifdef FL
	freopen(fout,"w",stdout);
#endif

	printf("%d\n",M);

	for (i=1;i<=N;++i)
	for (j=1;j<=N;++j)
		if (F[i][N+j] == 1)
			printf("%d %d\n",i,j);
}

int main()
{
	readdata();
	flux();
	printdata();
	return 0;
}