Cod sursa(job #18766)

Utilizator mockeBarca Cristian Mihai mocke Data 18 februarie 2007 13:59:41
Problema Adapost Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.61 kb

#include<stdio.h>
#include<string.h>
#include <math.h>
#include <vector>
#include <algorithm>
#define PB push_back
#define MP make_pair
#define EPS 1e-6
#define ABS(a) ( (a) < 0 ? -(a) : (a) )
#define MIN(a, b) ( (a) < (b) ? (a) : (b) )
#define NMAX 825
#define INF 100000001

using namespace std;

vector <double> Dist;
int Adj[NMAX][NMAX];
double Cost[NMAX][NMAX];

struct per { double x, y; } V[NMAX];

int L[NMAX], R[NMAX], U[NMAX];
int P[NMAX], Q[NMAX*NMAX];
int C[NMAX][NMAX], F[NMAX][NMAX];
int N, NN;
int i, j, Nr, FLX;
int l, r, c;
double D[NMAX];
double cost_, CST, minm;

void unite_n(int x, int y, double z, int capa)
{
        C[x][y] = capa;
        
		Adj[x][++Adj[x][0]] = y, Adj[y][++Adj[y][0]] = x;
		Cost[x][Adj[x][0]] = z, Cost[y][Adj[y][0]] = -z;
}

int PairUp(int x, double c_max)
{
	int i;
	int sz = Adj[x][0];
	
	if (U[x]) return 0;
	
	U[x] = 1;

	for (i = 1; i <= sz; i++)
		if ( Cost[x][i] < c_max || ABS( Cost[x][i] - c_max) < EPS )
			if ( R[Adj[x][i]] == -1 || PairUp(R[Adj[x][i]], c_max) )
			{
				R[L[x] = Adj[x][i]] = x;
			
				return 1;
			}
			
	return 0;
}

int augment(double c_max)
{
	memset(L, 0xFF, sizeof(L));
	memset(R, 0xFF, sizeof(R));
	memset(U, 0xFF, sizeof(U));

	for (i = 1; i <= NN/2; i ++)
		if (!PairUp(i, c_max))
		{
			memset(U, 0, sizeof(U));
			PairUp(i, c_max);
		}

	int Ans = 0;
	
	for (i = 1; i <= NN; i ++)
		if (L[i] != -1) ++ Ans;
	
	return Ans;
}

int Bellman_Ford()
{
	int i, j, sz, nod, ql, qr;
	double costul;

	memset(U, 0, sizeof(U));
	
	for (i = 0; i <= NN + 1; ++i) D[i] = +INF, P[i] = -1;
	
	ql = qr = 1;
	
	Q[ql] = 0, D[0] = 0.0, U[0] = 1;

	for (ql = 1; ql <= qr; ql++)
	{
		i = Q[ql], sz = Adj[i][0];
		
		for (j = 1; j <= sz; ++j)
		{
			nod = Adj[i][j], costul = Cost[i][j];
			
			if (C[i][nod] > F[i][nod] && D[nod] > D[i] + costul)
			{
					D[nod] = D[i] + costul;
					P[nod] = i;
				
					if (!U[nod]) U[Q[++qr] = nod] = 1;
			}
		}			
		
		if (i != 0) U[i] = 0;
	}	
	
	return D[NN + 1] < INF;
}

void maxflminc()
{
	int min, cap; 
	
	while( 1 )
	{
		if( Bellman_Ford() )
		{
				min = INF;

				for(i = NN + 1; P[i] >= 0; i = P[i])
				{
					cap = C[ P[i] ][i] - F[ P[i] ][i];

					if(min > cap) min = cap;
				}

				for(i = NN + 1; P[i] >= 0; i = P[i])
				{
							F[ P[i] ][i] += min;
							F[i][ P[i] ] -= min;
				}
				
				CST += min * D[NN + 1];
		}
		else break;
	}
}
int main()
{

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

	scanf("%d", &N);

	NN = 2 * N;

	for (i = 1; i <= NN; i++) scanf("%lf %lf", &V[i].x, &V[i].y);

	for (i = 1; i <= N; i++)
		for (j = N + 1; j <= NN; j++)
		{
			cost_ = sqrt( (V[j].x - V[i].x) * (V[j].x - V[i].x) + (V[j].y - V[i].y) * (V[j].y - V[i].y) );
			
			Dist.PB(cost_);
			
			unite_n(i, j, cost_, 1);
		}
	 
	sort(Dist.begin(), Dist.end());
	
	l = 0, r = Dist.size() - 1;
	
	minm = INF;
	
	while (l <= r)
	{ 
		c = (l + r) / 2;
		
		FLX = augment(Dist[c]);
		
		if (FLX == N) r = c - 1, minm = MIN(Dist[c], minm);
		else 		  l = c + 1;
	}
	
	memset(F, 0, sizeof(F));
	
	for (i = 1; i <= N; i++) memset(Adj[i], 0, sizeof(Adj[i]));
	
	for (i = 1; i <= N; i++) unite_n(0, i, 0.0, 1);
	
	for (i = 1; i <= N; i++)
		for (j = N + 1; j <= NN; j++)
		{
			cost_ = sqrt( (V[j].x - V[i].x) * (V[j].x - V[i].x) + (V[j].y - V[i].y) * (V[j].y - V[i].y) );
			
			if ( ABS(cost_ - minm) < EPS || cost_ < minm) unite_n(i, j, cost_, 1);
		}
	
	for (i = N + 1; i <= NN; i++) unite_n(i, NN + 1, 0.0, 1);

	maxflminc();
	
	printf("%.5lf %.5lf\n", minm, CST);
	
	return 0;
}