Cod sursa(job #566066)

Utilizator savimSerban Andrei Stan savim Data 28 martie 2011 17:04:29
Problema Adapost Scor 18
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.12 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.00000001

int n, m, s, d;

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], Q[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] = -dist(i, j);
			}
}

void get_distance() {
	for (int i = 1; i <= d; i++)
		D[i] = inf;
	D[s] = 0;
	
	for (int iterations = 0; iterations < d; iterations++) {
		bool update = 0;
		
		for (int i = 1; i <= d; i++)
			for (vector <int>::iterator it = G[i].begin(); it != G[i].end(); ++it)
				if (C[i][*it] && D[i] + cost[i][*it] < D[*it]) {
					D[*it] = D[i] + cost[i][*it];
					update = true;
				}
		
		if (!update)
			break;
	}
}

void update_flow_graph() {
	for (int i = 1; i <= d; i++)
		for (vector <int>::iterator it = G[i].begin(); it != G[i].end(); ++it)
			if (D[i] != inf && D[*it] != inf) 
				cost[i][*it] = cost[i][*it] + D[i] - D[*it];
}

double dijkstra() {
	update_flow_graph();

	for (int iterations = 1; iterations <= d; iterations++) {
		double value = inf;
		int pos = s;
		
		for (int i = 1; i <= d; i++)
			if (D[i] < value && viz[i] == 0) {
				value = D[i];
				pos = i;
			}

		if (pos == d || value == inf)
			break;
		else 
			viz[pos] = 1;
			
		for (vector <int>::iterator it = G[pos].begin(); it != G[pos].end(); ++it)
			if (C[pos][*it] > F[pos][*it] && D[*it] > D[pos] + cost[pos][*it]) {
				D[*it] = D[pos] + cost[pos][*it];
				tata[*it] = pos;
			}
	}
	
	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();

	get_distance();
	
	improve = true;
	while (improve) {
		improve = false;
		
		for (int i = 1; i <= d; i++) {
			D[i] = inf;
			viz[i] = tata[i] = 0;
		}
		D[s] = 0;
		
		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;
}