Cod sursa(job #402646)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 24 februarie 2010 00:13:46
Problema Adapost Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.68 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;

#define file_in "adapost.in"
#define file_out "adapost.out"

#define Nmax 500
#define Inf 0x3f3f3f3f

vector<int> G[Nmax*Nmax];
vector<int> G1[Nmax*Nmax];
int viz[Nmax*Nmax];
int cuplaj1[Nmax*20];
int cuplaj2[Nmax*20];
struct ad
{
	int x,y;
	double c;
}
v[Nmax*Nmax];
int nr,n;
double a1[Nmax],b2[Nmax];
double a2[Nmax],b1[Nmax];
double C[Nmax][Nmax];
double P[Nmax][Nmax];
double F[Nmax][Nmax];
int S,D;
double q[Nmax*Nmax];
int t[Nmax];

inline double dist(double x1, double y1, double x2, double y2)
{
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

int cmp(ad a, ad b)
{
	return (a.c<b.c);
}

int cuplaj(int nod)
{
	int x;
	if (viz[nod]==1)
		return 0;
	
	viz[nod]=1;
	
	for (int i=0;i<G[nod].size();++i)
	{
		x=G[nod][i];
		if (cuplaj1[x]==0)
		{
			cuplaj2[nod]=1;
			cuplaj1[x]=nod;
			return 1;
		}
	}
	
	for (int i=0;i<G[nod].size();++i)
	{
		x=G[nod][i];
		if (cuplaj1[x]!=nod && cuplaj(cuplaj1[x]))
		{
			cuplaj2[nod]=1;
			cuplaj1[x]=nod;
			return 1;
		}
	}
	
	return 0;
}


int good(double nod)
{
	int i,ok,nrr;
	for (i=1;i<=nr;++i)
		 G[i].clear();
	memset(cuplaj1,0,sizeof(cuplaj1));
	memset(cuplaj2,0,sizeof(cuplaj2));
	
	//contruieste noul graf
	
	for (i=1;i<=nr && v[i].c<=nod;++i)
		 G[v[i].x].push_back(v[i].y);
	
	nrr=0;
	///baga cuplaj
	ok=1;
	while(ok)
	{
		ok=0;
		memset(viz,0,sizeof(viz));
		for (i=1;i<=n;++i)
			 if (cuplaj2[i]==0 && cuplaj(i))
			 {
				 nrr++;
				 ok=1;
			 }
	}
	
	return (n==nrr);
}

int bf()
{
	memset(q,0x3f3f3f3f,sizeof(q));
	queue<int> Q;
	memset(viz,0,sizeof(viz));
	int x;
	Q.push(S);
	t[S]=0;
	viz[S]=1;
	q[S]=0;
	for(;!Q.empty();Q.pop())
	{
		x=Q.front();
		viz[x]=0;
		for (int i=0;i<G1[x].size();++i)
		{
			int nod=G1[x][i];
			if (q[nod]>q[x]+C[x][nod] && C[x][nod]-F[x][nod]>0)
			{
				q[nod]=q[x]+C[x][nod];
				viz[nod]=1;
				Q.push(nod);
				t[nod]=x;
			}
		}
		//Q.pop();
	}
	
	if (q[D]==0x3f3f3f3f) 
		return 0;
	else
		return 1;
}
	

void baga_flux()
{
	double cost=0.0;
	double vv;
	for(;bf();)
	{
		vv=0x3f3f3f3f;
		for (int i=D;i!=S;i=t[i])
			 vv=min(vv,F[t[i]][i]);
		for (int i=D;i!=S;i=t[i])
		     F[i][t[i]]+=vv,
			 F[t[i]][i]-=vv;
		
		cost+=q[D];
	}
	printf("%.5lf",cost);
}	



int main()
{
	int i,ls,ld,sol,mij,j;
    double d;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d", &n);
	for (i=1;i<=n;++i)
		scanf("%lf %lf", &a1[i], &b1[i]); 
	for (i=1;i<=n;++i)
		scanf("%lf %lf", &a2[i], &b2[i]); 
    
	//formez distantele
	S=0;
	D=2*n+1;
	nr=0;
	for (i=1;i<=n;++i)
		 for (j=1;j<=n;++j)
		 {
			 d=dist(a1[i],b1[i],a2[j],b2[j]);
			 v[++nr].c=d;
			 v[nr].x=i;
			 v[nr].y=j;
			 G1[i].push_back(j+n);
		     G1[j+n].push_back(i);
		
		     C[i][j+n]=d;
		     C[j+n][i]=-d;
		     F[i][j+n]=1;
		 }
	for (i=1;i<=n;++i)
	{
		G1[S].push_back(i);
		G1[i].push_back(S);
		F[S][i]=1;
	}
	for (i=n+1;i<=2*n;++i)
	{
		G1[D].push_back(i);
		G1[i].push_back(D);
		F[i][D]=1;
	}

		 
	//sorteaza in functie de distanta
     sort(v+1,v+nr+1,cmp);		 
	 
	 /*for (i=1;i<=nr;++i)
         printf("%.5lf\n", v[i].c);	*/
	//cautare binara intervalu [1,nr]	
    ls=1;
    ld=nr;
    while(ls<=ld)
	{
		mij=(ls+ld)>>1;
		
		if (good(v[mij].c))
		{
			sol=mij;
			ld=mij-1;
		}
		else
		{
			ls=mij+1;
		}
	}

	printf("%.5lf ", v[sol].c);
	//S=1;//sursa
	//D=n;//destinatia
	
	
	//a doua cerinta
	//cuplaj maxim de cost minim
	baga_flux();
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}