Cod sursa(job #682256)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 18 februarie 2012 19:43:08
Problema Adapost Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.16 kb
#include <fstream>
#include <vector>
#include <queue>
#include <iomanip>
#include <math.h>
#include <algorithm>
#define NMAx 810
#define oo (1<<30)
#define pb push_back
#define dist(a,b,c,d) sqrt((a-b)*(a-b)+(c-d)*(c-d))
using namespace std;

vector <int> G[NMAx];
vector <double> v;
queue <int> Q;
int n,S,D,color,inQ[NMAx],tata[NMAx];
int viz[NMAx],L[NMAx],R[NMAx];
double sol,e,Cost[NMAx][NMAx],dist[NMAx];
double X[NMAx],Y[NMAx];
bool Flux[NMAx][NMAx];

void reset_graph() {
	
	for(int i=1;i<=2*n;i++) {
		G[i].clear();
		L[i]=R[i]=0;
		}
	
}
bool BF() {
	
	int i,nod,vecin;
	
	for(i=S;i<=D;i++)
		dist[i]=oo;
	
	dist[S]=0;
	Q.push(S);
	color++;
	
	while(!Q.empty()) {
		
		nod=Q.front();
		Q.pop();
		inQ[nod]=false;
		
		for(i=0;i<G[nod].size();i++) {
			
			vecin=G[nod][i];
			
			if(Flux[nod][vecin]>0&&dist[vecin]>dist[nod]+Cost[nod][vecin]) {
				dist[vecin]=dist[nod]+Cost[nod][vecin];
				tata[vecin]=nod;
				if(inQ[nod]!=color) {
					Q.push(vecin);
					inQ[vecin]=color;
					}
				}
			}
		}
	
	if(dist[D]==oo)
		return 0;
	return 1;
	
}
void bulid_flow_network() {
	
	int i,j;
	double d;
	
	S=0;
	D=2*n+1;
	reset_graph();
	
	for(i=1;i<=n;i++) {
		G[S].pb(i);
		Flux[S][i]=1;
		}
	
	for(i=1;i<=n;i++)
		for(j=n+1;j<=2*n;j++) {
			d=dist(X[i],X[j],Y[i],Y[j]);
			if(d>e)
				continue;
			G[i].pb(j);
			Flux[i][j]=1;
			Cost[i][j]=d;
			
			G[j].pb(i);
			Cost[j][i]=-d;
			}
		
	for(i=n+1;i<=2*n;i++) {
		G[i].pb(D);
		Flux[i][D]=1;
		}

}
bool cuplaj(int nod) {
	
	int i;
	
	if(viz[nod]==color)
		return 0;
	else
		viz[nod]=color;
	
	for(i=0;i<G[nod].size();i++)
		if(!L[G[nod][i]]) {
			L[G[nod][i]]=nod;
			R[nod]=G[nod][i];
			return 1;
			}
		
	for(i=0;i<G[nod].size();i++)
		if(cuplaj(L[G[nod][i]])) {
			L[G[nod][i]]=nod;
			R[nod]=G[nod][i];
			return 1;
			}

	return 0;
	
}
int solution(double k) {
	
	int i,j,ok=1,nr=0;
	
	reset_graph();
	
	for(i=1;i<=n;i++)
		for(j=n+1;j<=2*n;j++)
			if(dist(X[i],X[j],Y[i],Y[j])<=k)
				G[i].pb(j);
			
	while(ok) {
		ok=0;
		color++;
		
		for(i=1;i<=n;i++)
			if(!R[i]&&cuplaj(i)) {
				nr++;
				ok=1;
				}
		}
		
	return nr;
	
}
int binary_search() {
	
	int i,step;
	
	for(step=1;step<v.size();step<<=1);
	
	for(i=0;step;step>>=1)
		if(i+step<v.size()&&solution(v[i+step])<n)
			i+=step;
		
	return i+1;
	
}
void citire() {
	
	ifstream in("adapost.in");
	in>>n;
	
	for(int i=1;i<=2*n;i++)
		in>>X[i]>>Y[i];
	
	in.close();
	
}
void afis() {

	ofstream out("adapost.out");
	out<<fixed<<setprecision(5)<<e<<' ';
	out<<fixed<<setprecision(5)<<sol<<'\n';
	out.close();
	
}
int main() {
	
	int i,j,flow,nod;
	
	citire();
	
	for(i=1;i<=n;i++)
		for(j=n+1;j<=2*n;j++)
			v.pb(dist(X[i],X[j],Y[i],Y[j]));
	sort(v.begin(),v.end());
	
	e=v[binary_search()];
	
	bulid_flow_network();
	
	color=0;
	while(BF()) {
		
		flow=oo;
		
		for(nod=D;nod!=S;nod=tata[nod])
			flow=min(flow,(int)Flux[tata[nod]][nod]);
		
		for(nod=D;nod!=S;nod=tata[nod]) {
			Flux[tata[nod]][nod]-=flow;
			Flux[nod][tata[nod]]+=flow;
			}
		
		sol+=dist[D];
		}
	
	afis();

	return 0;
	
}