Cod sursa(job #407638)

Utilizator jupanubv92Popescu Marius jupanubv92 Data 2 martie 2010 15:17:40
Problema Taramul Nicaieri Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include<stdio.h>
#include<vector>
#include<queue>
#include<string.h>
#define Nmx 202
#define INF 10000001

using namespace std;

int n,gri[Nmx],viz[Nmx],gre[Nmx],prec[Nmx];
int C[Nmx][Nmx],F[Nmx][Nmx],cpl,N;

vector <int> G[Nmx];
queue <int> Q;

void citire()
{
	scanf("%d",&n);
	N=n+n+1;
	for(int i=1;i<=n;++i)
	{
		scanf("%d%d",&gre[i],&gri[i]);
		C[0][i]=gre[i];
		C[i+n][N]=gri[i];
		G[0].push_back(i);
		G[i+n].push_back(N);
		for(int j=1;j<=n;++j)
			if(i!=j)
			{
				G[i].push_back(j+n);
				C[i][j+n]=1;
			}
	}
}

int bfs()
{

	vector <int> :: iterator it;
	memset(viz,0,sizeof(viz));
	memset(prec,-1,sizeof(prec));
	Q.push(0);
	viz[0]=1;
	while(!Q.empty())
	{
		int nod=Q.front();
		Q.pop();
		for(it=G[nod].begin();it!=G[nod].end();++it)
            if(C[nod][*it]-F[nod][*it]>0&&!viz[*it])
            {
                viz[*it]=1;
                prec[*it]=nod;
                Q.push(*it);
            }
	}
	return viz[N];
}



int min(int x,int y)
{
	if(x<y)
		return x;
	return y;
}


void solve()
{
	
	while(bfs())
	{
		for(int j=0;j<=N;++j)
		{
			if(C[j][N]-F[j][N]>0&&viz[j])
			{
				int Vmin=C[j][N]-F[j][n];
				for(int i=j;i!=0;i=prec[i])
					Vmin=min(Vmin,C[prec[i]][i]-F[prec[i]][i]);
				F[j][N]+=Vmin;
				F[N][j]-=Vmin;
				for(int i=j;i!=0;i=prec[i])
				{
					F[prec[i]][i]+=Vmin;
					F[i][prec[i]]-=Vmin;
				}
				cpl+=Vmin;
			}
		}
	}		
}

void afis()
{
	printf("%d\n",cpl);
	for(int i=1;i<=n;++i)
		for(int j=n+1;j<=n+n;++j)
			if(F[i][j]&&i!=j-n)
				printf("%d %d\n",i,j-n);
}	

int main()
{
	freopen("harta.in","r",stdin);
	freopen("harta.out","w",stdout);
	citire();
	solve();
	afis();
	return 0;
}