Cod sursa(job #342980)

Utilizator CezarMocanCezar Mocan CezarMocan Data 24 august 2009 15:36:22
Problema Adapost Scor 19
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.23 kb
#include <cstdio>
#include <vector>
#include <math.h>
#include <cstring>
#include <cassert>
#define maxn 810
#define inf 0x3f3f3f3f

using namespace std;

struct punct {
	int x, y;
};

int n, i, j;
double aa, bb;
vector <int> g[maxn], cost[maxn];
char f[maxn][maxn];
bool c[maxn][maxn];
int dist[maxn][maxn];
int dmin[maxn];
short int up[maxn];
punct v[maxn];
int dmax, sum;
int dst_min, cst_min;
short int src, dst;
bool ok, viz[maxn];
int heap[2 * maxn], heap_sz, poz_heap[maxn];
short int q[maxn * maxn];

inline int min(int a, int b) {
	if (a < b)
		return a;
	return b;
}

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

inline void fill(int v[], int val) {
	int i;
	for (i = 0; i < dst + 10; i++)
		v[i] = val;
}

inline void build_graf(int dmax) {
	int i;

	memset(f, 0, sizeof(f));		

	for (i = 0; i <= 2 * n + 1; i++) {
		g[i].clear(); cost[i].clear();
	}


	for (i = 1; i <= n; i++) {
		g[i].push_back(src); cost[i].push_back(0);
		g[src].push_back(i); cost[src].push_back(0);
		c[src][i] = 1; 
		f[src][i] = f[i][src] = 0;
	}

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

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

void bellman_ford() {
	int p, u;
	int nod, fiu, i;

	p = u = 1;
	q[1] = src;
	viz[src] = 1;
	dmin[src] = 0;

	while (p <= u) {
		nod = q[p];
		viz[nod] = 0;
		for (i = 0; i < g[nod].size(); i++) if (nod < g[nod][i]) {
			fiu = g[nod][i];
			if (dmin[fiu] > dmin[nod] + cost[nod][i]) {
				dmin[fiu] = dmin[nod] + cost[nod][i];
				if (viz[fiu] == 0) {
					u++;
					q[u] = fiu;
					viz[fiu] = 1;
				}
			}
		}
		p++;
	}

	sum = dmin[dst];

}

inline void init() {
	memset(up, -1, sizeof(up));
	memset(dmin, 0x3f, sizeof(dmin));
	dmin[src] = 0;
	ok = 0;
}

inline void swap(int &a, int &b) {
	int aux;
	aux = a; a = b; b = aux;
}

inline void heap_up(int no) {
	int nod = no;
	while (nod > 1) {
		if (dmin[heap[nod]] < dmin[heap[nod / 2]]) {
			swap(heap[nod], heap[nod / 2]);
			poz_heap[heap[nod]] = nod;
			poz_heap[heap[nod / 2]] = nod / 2;
			nod /= 2;
		}
		else
			break;
	}
}

inline void heap_down(int no) {
	int nod = no;
	while (2 * nod <= heap_sz) {
		if (dmin[heap[nod]] > min(dmin[heap[2 * nod]], dmin[heap[2 * nod + 1]])) {
			if (dmin[heap[2 * nod]] < dmin[heap[2 * nod + 1]]) {
				swap(heap[nod], heap[2 * nod]);
				poz_heap[heap[nod]] = nod;
				poz_heap[heap[2 * nod]] = 2 * nod;
				nod = 2 * nod;
			}
			else {
				swap(heap[nod], heap[2 * nod + 1]);
				poz_heap[heap[nod]] = nod;
				poz_heap[heap[2 * nod + 1]] = 2 * nod + 1;
				nod = 2 * nod + 1;
			}
		}
		else
			break;
	}
}

inline int dijkstra() {
	int i, j, nod, fiu, fmin;

	for (i = src; i <= dst; i++)
		for (j = 0; j < g[i].size(); j++) {
			fiu = g[i][j];
			if (dmin[i] != inf && dmin[fiu] != inf)
				cost[i][j] += dmin[i] - dmin[fiu];
		}

	init();

	for (i = src; i <= dst; i++) {
		heap[i + 1] = i;
		poz_heap[i] = i + 1;
	}

	heap_sz = dst + 1;
	heap[heap_sz + 1] = heap[heap_sz + 2] = dst + 1;

	while (heap_sz > 1 && dmin[heap[1]] != inf) {
		nod = heap[1];
		int gs = g[nod].size();
		for (i = 0; i < gs; i++) {
			fiu = g[nod][i];
			if (f[nod][fiu] < c[nod][fiu] && dmin[nod] + cost[nod][i] < dmin[fiu]) {
				dmin[fiu] = dmin[nod] + cost[nod][i];
				up[fiu] = nod;
				heap_up(poz_heap[fiu]);
			}
		}

		heap[1] = heap[heap_sz];
		heap[heap_sz] = dst + 1;
		heap_sz--;
		heap_down(1);
	}

	if (dmin[dst] == inf) 
		return 0;

	ok = 1;

	fmin = inf;
	for (i = dst; i != src; i = up[i]) 
		fmin = min(fmin, c[up[i]][i] - f[up[i]][i]);

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

	sum += dmin[dst];
	return (sum * fmin);
}

inline int posibil(int dist_max) {
	int nrp, cost;
	build_graf(dist_max);

	dmin[src] = 0;
	bellman_ford();

	ok = 1; nrp = 0; cost = 0;
	while (ok) {
		cost += dijkstra();
		nrp++;
	}

	if (nrp > n)
		return cost;
	else
		return -1;
}

inline void bsearch(int left, int right) {
	int m, p;
	while (left <= right) {
		m = (left + right) / 2;
		p = posibil(m);
		if (p != -1) {
			if (m < dst_min) {
				dst_min = m;
				cst_min = p;
			}
			right = m - 1;
		}
		else
			left = m + 1;
	}
}

inline void init_src_dst() {
	src = 0; dst = 2 * n + 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", &aa, &bb);
		v[i].x = (int)(aa * 1000);
		v[i].y = (int)(bb * 1000);
	}

	for (i = 1; i <= n; i++) 
		for (j = n + 1; j <= 2 * n; j++) {
			dist[i][j] = dist[j][i] = distanta(v[i], v[j]);
			dmax = max(dmax, dist[i][j]);
		}

	dst_min = inf; cst_min = inf;
	init_src_dst();
	bsearch(0, dmax);

	printf("%d.", dst_min / 1000);
	int aux = dst_min % 1000;
	if (aux)
		while (aux < 100) {
			printf("0");
			aux *= 10;
		}
	printf("%d ", dst_min % 1000);

	printf("%d.", cst_min / 1000);
	aux = cst_min % 1000;
	if (aux)
		while (aux < 100) {
			printf("0");
			aux *= 10;
		}
	printf("%d ", cst_min % 1000);

	return 0;
}