Cod sursa(job #428321)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 29 martie 2010 10:00:45
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <stdio.h>
#include <string.h>
#include <vector>
#define NMAX 102
#define LMAX 202
#define HMAX 10005
#define INF 0x3f3f3f3f
#define pb push_back
using namespace std;
int n,C[LMAX][LMAX],F[LMAX][LMAX],Q[LMAX],dad[LMAX],r;
int flow,fmin;
struct date
{
	int a,b;
};
date B[NMAX],sol[HMAX];
vector <int> A[LMAX];
char viz[LMAX];
void read()
{
	scanf("%d",&n);
	int i;
	for (i=1; i<=n; i++)
		scanf("%d%d",&B[i].a,&B[i].b);
}
void prepare()
{
	int i,j;
	for (i=1; i<=n; i++)
		for (j=n+1; j<=2*n; j++)
			if (i!=j-n)
			{
				C[i][j]=1;
				A[i].pb(j);
				A[j].pb(i);
			}
	for (i=1; i<=n; i++)
	{
		C[0][i]=B[i].a;
		A[0].pb(i);
		A[i].pb(0);
	}
	for (i=n+1; i<=2*n; i++)
	{
		C[i][2*n+1]=B[i-n].b;
		A[i].pb(2*n+1);
		A[2*n+1].pb(i);
	}
}
inline int min(int x,int y)
{
	return x<y ? x : y;
}
int BF()
{
	Q[0]=1; Q[1]=0;
	memset(viz,0,sizeof(viz));
	viz[0]=1;
	int i,j,nod,vec;
	for (i=1; i<=Q[0]; i++)
	{
		nod=Q[i];
		for (j=0; j<A[nod].size(); j++)
		{
			vec=A[nod][j];
			if (C[nod][vec]==F[nod][vec] || viz[vec])
				continue ;
			viz[vec]=1;
			Q[++Q[0]]=vec;
			dad[vec]=nod;
			if (vec==2*n+1)
				return 1;
		}
	}
	return 0;
}
void solve()
{
	int nod;
	while (BF())
	{
		fmin=INF;
		for (nod=2*n+1; nod!=0; nod=dad[nod])
			fmin=min(fmin,C[dad[nod]][nod]-F[dad[nod]][nod]);
		for (nod=2*n+1; nod!=0; nod=dad[nod])
		{
			F[dad[nod]][nod]+=fmin;
			F[nod][dad[nod]]-=fmin;
		}
		flow+=fmin;
	}
}
void get_sol()
{
	int i,j;
	for (i=1; i<=n; i++)
		for (j=n+1; j<=2*n; j++)
			if (F[i][j])
				sol[++r].a=i, sol[r].b=j-n;
}
void show()
{
	int i;
	printf("%d\n",r);
	for (i=1; i<=r; i++)
		printf("%d %d\n",sol[i].a,sol[i].b);
}
int main()
{
	freopen("harta.in","r",stdin);
	freopen("harta.out","w",stdout);
	read();
	prepare();
	solve();
	get_sol();
	show();
	return 0;
}