Cod sursa(job #433324)

Utilizator vladbBogolin Vlad vladb Data 3 aprilie 2010 16:10:52
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<fstream>

using namespace std;

ifstream fin("harta.in");
ofstream fout("harta.out");

int n,m,S,T,flow;
int c[202][202],f[202][202],di[101],de[101],x[202],t[202],pus[202];

void augment()
{	int j=T,i;
	while(j!=S)
	{	i=abs(t[j]);
		if(t[j]>=0) f[i][j]++;
		else f[j][i]--;
		j=i;
	}
	flow++;
}

int bf()
{	int st=1,dr=1,i;
	for(i=1;i<=T;i++)
	{	t[i]=0;
		pus[i]=0;
		x[i]=0;
	}
	x[1]=S;
	pus[S]=1;
	while(st<=dr)
	{	int nod=x[st];
		for(i=1;i<=T;i++)
			if(pus[i]==0)
			{	if(c[nod][i]>f[nod][i])
				{	x[++dr]=i;
					pus[i]=1;
					t[i]=nod;
					if(i==T) return 1;
				}
				if(f[i][nod])
				{	x[++dr]=i;
					pus[i]=1;
					t[i]=-nod;
					if(i==T) return 1;
				}
			}
		st++;
	}
	return 0;
}

void flux()
{	while(bf())
		augment();
}

int main()
{	int i,j;
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>de[i]>>di[i];
	for(i=1;i<=n;i++)
		for(j=n+1;j<=2*n;j++)
			if(i!=j-n) c[i][j]=1;
	S=0;
	T=2*n+1;
	for(i=1;i<=n;i++)
	{	c[0][i]=de[i];
		c[i+n][T]=di[i];
	}
	flux();
	fout<<flow<<"\n";
	for(i=1;i<=n;i++)
		for(j=n+1;j<=T;j++)
			if(f[i][j]) fout<<i<<" "<<j-n<<"\n";
	fin.close();
	fout.close();
	return 0;
}