Cod sursa(job #328755)

Utilizator savimSerban Andrei Stan savim Data 3 iulie 2009 12:18:35
Problema Adapost Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.05 kb
#include <stdio.h>
#include <math.h>
#include <vector>
#include <string.h>
#include <algorithm>

using namespace std;

#define MAX_N 1010
#define inf 2000000000
#define pb push_back

int n, t, improve, nr;
int C[MAX_N][MAX_N], F[MAX_N][MAX_N];
int tata[MAX_N], use[MAX_N], Q[MAX_N * MAX_N];
double dist[MAX_N], sol, ValMin, SumMin;

vector <int> G[MAX_N];

double cost[MAX_N][MAX_N], d[MAX_N][MAX_N], v[MAX_N * MAX_N];

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

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

void get_dist() {
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			d[i][j] = distanta(S[i], A[j]);
			v[++t] = d[i][j];
		}

	sort(v + 1, v + t + 1);
}

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

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

	//calculez distanta intre fiecare soldat si fiecare adapost
	get_dist();
}

void get_graph(double x) {
	for (int i = 1; i <= 2 * n + 2; i++)
		G[i].clear();

	memset(C, 0, sizeof(C));
	memset(F, 0, sizeof(F));
	memset(cost, 0, sizeof(cost));

	for (int i = 1; i <= n; i++) {
		C[1][i + 1] = C[n + i + 1][2 * n + 2] = 1;

		G[1].pb(i + 1); G[i + 1].pb(1);
		G[n + i + 1].pb(n * 2 + 2); G[n * 2 + 2].pb(n + i + 1);
	}

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) 
			if (d[i][j] <= x) {
				C[i + 1][n + j + 1] = 1;
				cost[i + 1][n + j + 1] = d[i][j];
				cost[n + j + 1][i + 1] = -d[i][j];
				
				G[i + 1].pb(n + j + 1);
				G[n + j + 1].pb(i + 1);
			}
}

void bellman_ford() {
	memset(use, 0, sizeof(use));
	memset(tata, -1, sizeof(tata));

	for (int i = 1; i <= 2 * n + 2; i++)
		dist[i] = inf;
	dist[1] = 0;

	int st = 0, dr = 1;
	Q[1] = 1; use[1] = 1;

	while (st < dr) {
    	st++;

		int len = G[Q[st]].size();
		for (int i = 0; i < len; i++)
			if (C[Q[st]][G[Q[st]][i]] - F[Q[st]][G[Q[st]][i]] > 0 && dist[G[Q[st]][i]] > dist[Q[st]] + cost[Q[st]][G[Q[st]][i]]) {
				tata[G[Q[st]][i]] = Q[st];
				dist[G[Q[st]][i]] = dist[Q[st]] + cost[Q[st]][G[Q[st]][i]];

				if (use[G[Q[st]][i]] == 0) {
					use[G[Q[st]][i]] = 1;
					Q[++dr] = G[Q[st]][i];
				}
			}
		use[Q[st]] = 0;
	}
	
	if (dist[2 * n + 2] < inf) {
		improve = 1;

		int flux = inf;
		for (int i = 2 * n + 2; i != 1; i = tata[i])
			flux = min(flux, C[tata[i]][i] - F[tata[i]][i]);

		for (int i = 2 * n + 2; i != 1; i = tata[i]) {
			F[tata[i]][i] += flux;
			F[i][tata[i]] -= flux;
		}
		
		nr++;
		sol += flux * dist[2 * n + 2];
	}
}

void solve() {
	int st = 0, dr = t + 1, mid = 0;

	ValMin = SumMin = inf;
/*	while (st + 1 < dr) {
		mid = (st + dr) / 2; */

		mid = t;

		get_graph(v[mid]);

		sol = 0;
		improve = 1; nr = 0;
		while (improve) {
			improve = 0; 
			
			bellman_ford();
		}

		if (nr == n) {
			if (v[mid] < ValMin) {
				ValMin = v[mid];
				SumMin = sol;		
			}
			
			dr = mid;
		}
		else st = mid;
//	}

	printf("%lf %lf\n", ValMin, SumMin);
}

int main() {

	cit();
	solve();

	return 0;
}