Cod sursa(job #564178)

Utilizator savimSerban Andrei Stan savim Data 26 martie 2011 20:40:42
Problema Adapost Scor 43
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.32 kb
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <vector>

using namespace std;

#define MAX_N 810
#define inf 1000000000

int n, m, s, d;

int viz[MAX_N], cuplaj[MAX_N];

double dmin, sol;

vector <int> G[MAX_N];

int 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)
				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 left = 0, right = 1000000;
	for (int iterations = 1; iterations <= 50; iterations++) {
		dmin = (left + right) / 2;

		get_graph(dmin);
    	
		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 = dmin;
		else
			left = dmin;
	}
}

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) {
            	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);
			}
}

double bf() {
	int st = 0, dr = 1;
	Q[1] = s; viz[s] = 1;

	while (st != dr) {
		st = st % d + 1;

		int nod = Q[st];
		for (vector <int>::iterator it = G[nod].begin(); it != G[nod].end(); ++it) {
        	int fiu = *it;

			if (C[nod][fiu] > F[nod][fiu] && D[fiu] > D[nod] + cost[nod][fiu]) {
            	D[fiu] = D[nod] + cost[nod][fiu];
				tata[fiu] = nod;

				if (viz[fiu] == 0) {
					dr = dr % d + 1;
                	Q[dr] = fiu;
					viz[fiu] = 1;
				}
			}
		}

		viz[nod] = 0;
	}

	if (D[d] < inf) {
		improve = 1;

		int flux = inf;
		for (int i = d; i != s; i = tata[i])
			flux = min(flux, C[tata[i]][i] - F[tata[i]][i]);
		
		for (int i = d; i != s; i = tata[i]) {
			F[tata[i]][i] += flux;
			F[i][tata[i]] -= flux;
		}

		return D[d];
	}

	return 0;
}

void solve() {
	get_dmin();	

	build_flow_graph();

	improve = 1;
	while (improve) {
		improve = 0;

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

		sol += bf();
	}

	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;
}