Cod sursa(job #581686)

Utilizator mihai995mihai995 mihai995 Data 14 aprilie 2011 14:58:16
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
using namespace std;

const int N=205;
int cap[N][N],flux[N][N],T[N],v[N],n;
bool use[N];

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

bool bfs(int X,int Y)
{
	int i,x,st=0,dr=0;
	for (i=1;i<=n;i++)
	{
		use[i]=false;
		T[i]=0;
	}
	v[++dr]=X;
	use[X]=true;
	while (st<dr)
	{
		x=v[++st];
		for (i=1;i<=n;i++)
			if (!use[i] && cap[x][i]>flux[x][i])
			{
				v[++dr]=i;
				T[i]=x;
				use[i]=true;
			}
	}
	return use[Y];
}

void max_flow(int X,int Y)
{
	int M,i,j;
	while (bfs(X,Y))
		for (i=0;i<=n;i++)
			if (cap[i][Y]>flux[i][Y])
			{
				M=cap[i][Y]-flux[i][Y];
				if (!M)
					continue;
				for (j=i;j!=X;j=T[j])
					M=min(M,cap[T[j]][j]-flux[T[j]][j]);
				if (!M)
					continue;
				T[Y]=i;
				for (j=Y;j!=X;j=T[j])
				{
					flux[T[j]][j]+=M;
					flux[j][T[j]]-=M;
				}
			}
}			

int main()
{
	int m,i,j,nr=0;
	in>>m;n=2*m+1;
	for (i=1;i<=m;i++)
	{
		in>>cap[0][i]>>cap[i+m][n];
		for (j=m+1;j<n;j++)
			cap[i][j]=1;
		cap[i][i+m]=0;
	}
	max_flow(0,n);
	for (i=1;i<=m;i++)
		for (j=m+1;j<n;j++)
			if (flux[i][j]>0)
				nr++;
	out<<nr<<"\n";
	for (i=1;i<=m;i++)
		for (j=m+1;j<n;j++)
			if (flux[i][j]>0)
				out<<i<<" "<<j-m<<"\n";
	return 0;
}