Cod sursa(job #708817)

Utilizator Robert29FMI Tilica Robert Robert29 Data 7 martie 2012 11:33:39
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include<stdio.h>
#include<vector>
using namespace std;
FILE*f=fopen("harta.in","r");
FILE*g=fopen("harta.out","w");
int n,nn,sol,p,u,minn,nod,c[204][204],L[204][204],viz[204],d[204],t[204];
struct nod
{
	int in,out;
}w[101];
vector <int> v[204];
int df()
{
	int ok=0;
	for(int i=0;i<=nn;++i)
		viz[i]=0;
	
	p=u=1;
	d[1]=0;
	viz[0]=1;
	while(p<=u)
	{
		for(int i=0;i<v[d[p]].size();++i)
			if(!viz[v[d[p]][i]]&&c[d[p]][v[d[p]][i]]-L[d[p]][v[d[p]][i]]>0)
			{
				if(v[d[p]][i]==nn)
					ok=1;
				else
				{
					t[v[d[p]][i]]=d[p];
					d[++u]=v[d[p]][i];
					viz[v[d[p]][i]]=1;
				}
			}
		++p;
	}
	return ok;
}
void dfs()
{
	for(int i=1;i<=n;++i)
		for(int j=n+1;j<nn;++j)
			if(L[i][j])
				fprintf(g,"%d %d\n",i,j-n);
}
int main()
{
	fscanf(f,"%d",&n);
	for(int i=1;i<=n;++i)
		fscanf(f,"%d%d",&w[i].out,&w[i].in);
	
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			if(i!=j)
			{
				v[i].push_back (j+n);
				v[j+n].push_back (i);
				c[i][j+n]=1;
			}
	
	for(int i=1;i<=n;++i)
	{
		v[0].push_back (i);
		v[i].push_back (0);
		v[i+n].push_back (2*n+1);
		v[2*n+1].push_back (i+n);
		c[0][i]=w[i].out;
		c[i+n][2*n+1]=w[i].in;
	}
	nn=2*n+1;	
	while(df())
	{
		for(int ii=0;ii<n;++ii)
		{
			minn=c[v[nn][ii]][nn]-L[v[nn][ii]][nn];
			for(int nod=v[nn][ii];nod;nod=t[nod])
				if(c[t[nod]][nod]-L[t[nod]][nod]<minn)
					minn=c[t[nod]][nod]-L[t[nod]][nod];
			
			L[v[nn][ii]][nn]+=minn;
			L[nn][v[nn][ii]]-=minn;
				
			for(int nod=v[nn][ii];nod;nod=t[nod])
			{
				L[t[nod]][nod]+=minn;
				L[nod][t[nod]]-=minn;
			}
			
			sol+=minn;
		}
		
	}
	
	fprintf(g,"%d\n",sol);
	
	dfs();
	
	fclose(g);
	fclose(f);
	return 0;
}