Cod sursa(job #329700)

Utilizator CezarMocanCezar Mocan CezarMocan Data 7 iulie 2009 10:58:07
Problema Adapost Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <cstdio>
#include <math.h>
#include <vector>
#define maxn 410
#define inf 2000000000

using namespace std;

struct punct {
	double x, y;
};

int n, i, j, src, dst, ok;
punct v[2 * maxn];
int dist[2 * maxn][2 * maxn];
int dmax, cmin, cst, flow, rez;
int f[2 * maxn][2 * maxn], c[2 * maxn][2 * maxn];
int ct[2 * maxn], up[2 * maxn], viz[2 * maxn];
int q[maxn * maxn];
vector <int> g[2 * maxn];

inline double distanta(punct a, punct b) {
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

void init() {
//	memset(up, -1, sizeof(up));
	memset(viz, 0, sizeof(viz));
	for (i = 0; i <= 2 * n + 1; i++)
		ct[i] = inf;
}

int bford() {
	int p, u;
	int nod, fiu, i;
	int unit;

	p = u = 1;
	q[1] = 0; viz[0] = 1; ct[0] = 0;

	while (p <= u) {
		nod = q[p];

		for (i = 0; i < g[nod].size(); i++) {
			fiu = g[nod][i];
			if (c[nod][fiu] - f[nod][fiu] > 0 && ct[fiu] > ct[nod] + dist[nod][fiu]) {
				ct[fiu] = ct[nod] + dist[nod][fiu];
				up[fiu] = nod;

				if (viz[fiu] == 0) {
					viz[fiu] = 1;
					u++;
					q[u] = fiu;
				}
			}
		}
		p++;
	}

	if (ct[dst] != inf) {
		ok = 1;
		unit = inf;
		for (nod = dst; nod != src; nod = up[nod])
			unit = min(unit, c[up[nod]][nod] - f[up[nod]][nod]);

		for (nod = dst; nod != src; nod = up[nod]) {
			f[up[nod]][nod] += unit;
			f[nod][up[nod]] -= unit;
		}

		flow += unit;
		return unit * ct[dst];
	}

	return 0;
}

bool solve(int d, int &cst) {
	//construiesc grafu si fac flux
	//toate muchiile existente o sa aiba capacitate 1
	for (i = 0; i <= 2 * n + 1; i++)
		g[i].clear();
	memset(f, 0, sizeof(f));
//	memset(c, 0, sizeof(c));

	src = 0;
	dst = 2 * n + 1;

	for (i = 1; i <= n; i++) {
		g[src].push_back(i);
		dist[src][i] = 0;
		c[src][i] = 1;
	}
	for (i = n + 1; i <= 2 * n; i++) {
		g[i].push_back(dst);
		c[i][dst] = 1;
		dist[i][dst] = 0;
	}

	for (i = 1; i <= n; i++)
		for (j = n + 1; j <= 2 * n; j++)
			if (dist[i][j] <= d) {
				g[i].push_back(j);
				g[j].push_back(i);
				dist[j][i] = -dist[i][j];
				c[i][j] = 1;
			}

	ok = 1; rez = 0;
	flow = 0;

	while (ok) {
		ok = 0;
		init();
		rez += bford();
	}

	if (flow == n) {
		cst = rez;
		return true;
	}

	return false;

}

void bsearch(int left, int right) {
	int m;
	while (left <= right) {
		m = (left + right) / 2;
//		fprintf(stderr, "%d\n", m);
		if (solve(m, cst)) {
			if (m < dmax) {
				dmax = m;
				cmin = cst;
			}
			right = m - 1;
		}
		else
			left = m + 1;
	}
}

int main() {
	freopen("adapost.in", "r", stdin);
	freopen("adapost.out", "w", stdout);
	scanf("%d", &n);
	for (i = 1; i <= 2 * n; i++)
		scanf("%lf%lf", &v[i].x, &v[i].y);

	for (i = 1; i <= 2 * n; i++)
		for (j = 1; j <= 2 * n; j++)
			dist[i][j] = (int) (1000 * distanta(v[i], v[j]));

	dmax = inf;
	bsearch(0, 1000000);

	printf("%d %d\n", dmax, cmin);

	return 0;
}