Cod sursa(job #1397888)

Utilizator stefanzzzStefan Popa stefanzzz Data 23 martie 2015 20:19:33
Problema Adapost Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.18 kb
#include <stdio.h>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <algorithm>
#define MAXN 420
#define EPS 1e-6
#define INF 1e6
#define x first
#define y second
using namespace std;

const int off = 405, start = 402, fin = 403;
int n, fx[2 * MAXN][2 * MAXN], cap[2 * MAXN][2 * MAXN];
double mxcost, totcost;
pair<double, double> pct[MAXN], ad[MAXN];
vector< pair<int, double> > G[2 * MAXN];
vector<double> vdist;
int L[MAXN], R[MAXN];
bool uzc[MAXN];

queue<int> q;
double dst[2 * MAXN];
bool uzq[2 * MAXN];
int bk[2 * MAXN];

inline double euclidianDist(pair<double, double> pa, pair<double, double> pb){
	double dx = pa.x - pb.x, dy = pa.y - pb.y;
	return sqrt(dx * dx + dy * dy);
}

bool pairup(int p, double &mxcost){
	if(uzc[p]) return 0;
	uzc[p] = 1;

	for(auto a: G[p])
		if(a.second < mxcost + EPS && !R[a.first]){
			L[p] = a.first;
			R[a.first] = p;
			return 1;
		}
	
	for(auto a: G[p])
		if(a.second < mxcost + EPS && pairup(R[a.first], mxcost)){
			L[p] = a.first;
			R[a.first] = p;
			return 1;
		}
	return 0;
}

int cuplaj(double &mxcost){
	int i, cupl = 0;
	bool change = 1;
	
	memset(L, 0, sizeof(L));
	memset(R, 0, sizeof(R));

	while(change){
		change = 0;
		memset(uzc, 0, sizeof(uzc));
		for(i = 1; i <= n; i++)
			if(!L[i])
				change |= pairup(i, mxcost);
	}

	for(i = 1; i <= n; i++)
		cupl += (L[i] != 0);
	return cupl;
}

bool BellmanFord(){
	int i, a;
	
	memset(uzq, 0, sizeof(uzq));
	memset(bk, 0, sizeof(bk));
	while(!q.empty()) q.pop();
	for(i = 1; i <= n + off; i++)
		dst[i] = INF;
	
	dst[start] = 0; 
	q.push(start); uzq[start] = 1;

	while(!q.empty()){
		a = q.front();
		q.pop(); uzq[a] = 0;

		for(auto b: G[a]){
			if(fx[a][b.first] < cap[a][b.first] && dst[a] + b.second < dst[b.first]){
				dst[b.first] = dst[a] + b.second;
				bk[b.first] = a;
				if(!uzq[b.first]){ uzq[b.first] = 1; q.push(b.first); }
			}
		}
	}

	return dst[fin] < INF;	
}

int main(){
	freopen("adapost.in", "r", stdin);
	freopen("adapost.out", "w", stdout);
	int i, j;

	scanf("%d", &n);
	for(i = 1; i <= n; i++)
		scanf("%lf %lf", &pct[i].x, &pct[i].y);
	for(i = 1; i <= n; i++)
		scanf("%lf %lf", &ad[i].x, &ad[i].y);
	
	for(i = 1; i <= n; i++)
		for(j = 1; j <= n; j++){
			G[i].push_back(make_pair(j, euclidianDist(pct[i], ad[j])));
			vdist.push_back(euclidianDist(pct[i], ad[j]));
		}

	sort(vdist.begin(), vdist.end());
	int l = 0, r = vdist.size() - 1, mid;
	
	while(l < r){
		mid = (l + r) >> 1;
		if(cuplaj(vdist[mid]) == n) r = mid - 1;
		else l = mid + 1;
	}
	while(r < 0 || cuplaj(vdist[r]) < n) r++;
	
	mxcost = vdist[r];
	for(i = 1; i <= n; i++)
		G[i].clear();
	
	for(i = 1; i <= n; i++)
		for(j = 1; j <= n; j++)
			if(euclidianDist(pct[i], ad[j]) < mxcost + EPS){
				G[i].push_back(make_pair(j + off, euclidianDist(pct[i], ad[j])));
				G[j + off].push_back(make_pair(i, -euclidianDist(pct[i], ad[j])));
				cap[i][j + off] = 1;
			}
	
	for(i = 1; i <= n; i++){
		G[start].push_back(make_pair(i, 0));
		G[i + off].push_back(make_pair(fin, 0));
		cap[start][i] = cap[i + off][fin] = 1;
	}

	while(BellmanFord()){
		int a = fin;

		totcost += dst[fin];
		while(bk[a]){
			fx[bk[a]][a]++;
			fx[a][bk[a]]--;
			a = bk[a];
		}
	}

	printf("%.7lf %.7lf\n", mxcost, totcost);

	return 0;
}