Cod sursa(job #533049)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 12 februarie 2011 22:27:00
Problema Adapost Scor 12
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.36 kb
#include <fstream>
#include <math.h>
using namespace std;
ifstream fin("adapost.in");
ofstream fout("adapost.out");

#include <vector>
#include <queue>
#define maxn 805
#define maxm 160005
#define oo 200000000
#define pb push_back

int i,j,N,nrM,srs,dest,k,flmin,m,st,dr,nrC;
struct coord { double x,y; } s[maxn],ad[maxn];
double M[maxm],Cost[maxn][maxn],D[maxn];
double MinDist,x,R,Rmax;
vector <int> A[maxn];
queue <int> Q;
int C[maxn][maxn],id[maxm],from[maxn],v[maxn];

inline double min(double a, double b)
{
	return a<b ? a : b;
}

void citire()
{
	fin >> N;
	for(i=1;i<=N;i++)
		fin >> s[i].x >> s[i].y;
	for(i=1;i<=N;i++)
		fin >> ad[i].x >> ad[i].y;
}

void constr()
{
	double val;
	for(i=1;i<=N;i++)
		for(j=1;j<=N;j++)
		{
			val=sqrt(pow(s[i].x-ad[j].x,2)+pow(s[i].y-ad[j].y,2));
			M[++nrM]=val;
			A[i].pb(j+N); A[j+N].pb(i);
			C[i][j+N]=1; Cost[i][j+N]=val; Cost[j+N][i]=-val;
		}
	srs=0; dest=2*N+1;
	for(i=1;i<=N;i++)
	{
		A[srs].pb(i); A[i].pb(srs);
		C[srs][i]=1;
		A[i+N].pb(dest); A[dest].pb(i+N);
		C[i+N][dest]=1;
	}
}

void sortare()
{
	for(i=1;i<=nrM;i++) id[i]=i;
	int aux;
	for(i=1;i<=nrM-1;i++)
		for(j=i+1;j<=nrM;j++)
			if(M[id[i]]>M[id[j]])
			{
				aux=id[i];
				id[i]=id[j];
				id[j]=aux;
			}
}

int BFS(double x)
{
	while(!Q.empty()) Q.pop();
	for(i=1;i<=dest;i++) v[i]=0;
	Q.push(srs); v[srs]=1;
	for(;!Q.empty();Q.pop())
	{
		k=Q.front();
		for(i=0;i<(int)A[k].size();i++)
			if(!v[A[k][i]] && C[k][A[k][i]]>0 && Cost[k][A[k][i]]<=x)
			{
				Q.push(A[k][i]);
				v[A[k][i]]=1;
				from[A[k][i]]=k;
				if(A[k][i]==dest)
					return 1;
			}
	}
	return 0;
}


int BF(double x)
{
	while(!Q.empty()) Q.pop();
	for(i=1;i<=dest;i++) { D[i]=oo; v[i]=0; }
	Q.push(srs); D[srs]=0; v[srs]=1;
	for(;!Q.empty();Q.pop())
	{
		k=Q.front();
			for(i=0;i<(int)A[k].size();i++)
			if(C[k][A[k][i]]>0 && Cost[k][A[k][i]]<=x)
				if(D[k]+Cost[k][A[k][i]]<D[A[k][i]])
				{
					D[A[k][i]]=D[k]+Cost[k][A[k][i]];
					from[A[k][i]]=k;
					if(!v[A[k][i]])
					{
						Q.push(A[k][i]);
						v[A[k][i]]=1;
					}
				}
		v[k]=0;
	}
	return D[dest]<oo;
}

int flux2(double x)
{
	nrC=0;
	for(i=1;i<=N;i++)
	{
		for(j=1;j<=N;j++)
		{
			C[i][j+N]=1;
			C[j+N][i]=0;
		}
		C[srs][i]=1; C[i][srs]=0;
		C[i+N][dest]=1; C[dest][i+N]=0;
	}
	while( BFS(x) )
	{
		flmin=oo;
		for(k=dest;k!=srs;k=from[k])
			flmin=min(flmin,C[from[k]][k]);
		for(k=dest;k!=srs;k=from[k])
		{
			C[from[k]][k]-=flmin;
			C[k][from[k]]+=flmin;
		}
		nrC+=flmin;
	}
	return nrC==N;
}

int flux(double x)
{
	R=0; nrC=0;
	for(i=1;i<=N;i++)
	{
		for(j=1;j<=N;j++)
		{
			C[i][j+N]=1;
			C[j+N][i]=0;
		}
		C[srs][i]=1; C[i][srs]=0;
		C[i+N][dest]=1; C[dest][i+N]=0;
	}
	while( BF(x) )
	{
		flmin=oo;
		for(k=dest;k!=srs;k=from[k])
			flmin=min(flmin,C[from[k]][k]);
		for(k=dest;k!=srs;k=from[k])
		{
			C[from[k]][k]-=flmin;
			C[k][from[k]]+=flmin;
		}
		R+=flmin*D[dest];
		nrC+=flmin;
	}
	return nrC==N;
}

void cb(int st, int dr)
{
	m=st+(dr-st)/2; MinDist=oo;
	while(st<=dr)
	{
		if( flux2(M[id[m]]) )
		{
			dr=m;
			MinDist=M[id[m]]; Rmax=R;
		}
		else
			st=m+1;
		if(st==m && st==dr) break;
		m=st+(dr-st)/2;
	}
}

int main()
{
	citire();
	constr();
	sortare();
	cb(1,nrM);
	fout.precision(7);
	fout << MinDist << '\n';
	fout << Rmax;
}