Cod sursa(job #791609)

Utilizator GrimpowRadu Andrei Grimpow Data 24 septembrie 2012 17:51:10
Problema Adapost Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.96 kb
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX_N 810
#define inf 1000000000

#define eps 0.000001

#define mp make_pair

int n, m, s, d, k;

int viz[MAX_N], cuplaj[MAX_N];

double dmin = inf, sol;

vector <int> G[MAX_N];

bool improve;

int C[MAX_N][MAX_N], F[MAX_N][MAX_N];
double cost[MAX_N][MAX_N];

int tata[MAX_N], h[MAX_N], pos[MAX_N];
double D[MAX_N];

struct punct {
	double x, y;
} A[MAX_N], B[MAX_N];

inline double dist(int p, int q) {
	return sqrt((A[p].x - B[q].x) * (A[p].x - B[q].x) + (A[p].y - B[q].y) * (A[p].y - B[q].y));
}

void get_graph(double k) {
	for (int i = 1; i <= n; i++)
		vector <int> ().swap(G[i]);

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (dist(i, j) <= k + eps)
				G[i].push_back(j);
}

bool cupleaza(int x) {
	if (viz[x])
		return false;
	viz[x] = 1;

	for (vector <int>::iterator it = G[x].begin(); it != G[x].end(); ++it)
		if (cuplaj[*it] == 0) {
        	cuplaj[*it] = x;
			m++;
			return true;
		}

	for (vector <int>::iterator it = G[x].begin(); it != G[x].end(); ++it)
		if (cuplaj[*it] != x && cupleaza(cuplaj[*it])) {
        	cuplaj[*it] = x;
			return true;
		}

	return false;
}

void get_dmin() {
	double value[MAX_N * MAX_N];
	
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			value[(i - 1) * n + j] = dist(i, j);
	sort(value + 1, value + n * n + 1);

	int left = 0, right = n * n + 1, mid = 0;
	while (left + 1 < right) {
		mid = (left + right) / 2;

		get_graph(value[mid]);

		memset(cuplaj, 0, sizeof(cuplaj)); m = 0;

		for (int i = 1; i <= n; i++) {
        	memset(viz, 0, sizeof(viz));
			cupleaza(i);
		}

		if (m == n) {
			right = mid;
        	dmin = min(dmin, value[mid]);
		}
		else
			left = mid;
	}
}

void build_flow_graph() {
	s = 1; d = 2 * n + 2;

	for (int i = 1; i <= d; i++)
		vector <int> ().swap(G[i]);

	for (int i = 1; i <= n; i++) {
		G[s].push_back(i + 1); C[s][i + 1] = 1;
		G[i + 1].push_back(s);

		G[n + i + 1].push_back(d); C[n + i + 1][d] = 1;
		G[d].push_back(n + i + 1);
	}

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (dist(i, j) <= dmin + eps) {
            	G[i + 1].push_back(n + j + 1); cost[i + 1][n + j + 1] = dist(i, j); C[i + 1][n + j + 1] = 1;
				G[n + j + 1].push_back(i + 1); cost[n + j + 1][i + 1] = -cost[i + 1][n + j + 1];
			}
}

void heap_update(int x) {
	//down-heap
	while (x > 1 && D[h[x / 2]] > D[h[x]]) {
    	swap(h[x], h[x / 2]);
		pos[h[x]] = x; pos[h[x / 2]] = x / 2;

		x /= 2;
	}

	//up-heap
	while ((x * 2 <= k && D[h[x * 2]] < D[h[x]]) || (x * 2 + 1 <= k && D[h[x * 2 + 1]] < D[h[x]])) {
		int nxt = x * 2;
		if (x * 2 + 1 <= k && D[h[x * 2 + 1]] < D[h[x * 2]])
			nxt = x * 2 + 1;

		swap(h[x], h[nxt]);
		pos[h[x]] = x; pos[h[nxt]] = nxt;

		x = nxt;
	}
}

double dijkstra() {
	for (int i = 1; i <= d; i++) {
    	D[i] = inf;
		tata[i] = viz[i] = 0;
	}
	D[s] = 0;

	h[k = 1] = s; pos[s] = viz[s] = 1;
	while (k) {
		int nod = h[1];

		swap(h[1], h[k]);
		pos[h[1]] = 1; pos[h[k]] = 0; k--;
		heap_update(1);
		
		viz[nod] = 0;

		for (vector <int>::iterator it = G[nod].begin(); it != G[nod].end(); ++it) {
			if (C[nod][*it] > F[nod][*it] && D[*it] > D[nod] + cost[nod][*it]) {
            	D[*it] = D[nod] + cost[nod][*it];

				if (viz[*it] == 0) {
                	h[++k] = *it;
					pos[*it] = k;
				}

				heap_update(pos[*it]);
				viz[*it] = 1;
				tata[*it] = nod;
			}
		}
	}

	if (D[d] != inf) {
		improve = true;

		for (int i = d; i != s; i = tata[i]) {
			F[tata[i]][i]++;
			F[i][tata[i]]--;
		}
	
		return D[d];
	}
	
	return 0;
}

void solve() {
	get_dmin();	

	build_flow_graph();

	improve = true;
	while (improve) {
		improve = false;
		
		sol += dijkstra();
	}
	
	printf("%lf %lf\n", dmin, sol);
}

int main() {

	freopen("adapost.in", "r", stdin);
	freopen("adapost.out", "w", stdout);

	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
		scanf("%lf %lf", &A[i].x, &A[i].y);
	for (int i = 1; i <= n; i++)
		scanf("%lf %lf", &B[i].x, &B[i].y);

	solve();

	return 0;
}