Cod sursa(job #17905)

Utilizator love_for_uSpancioc Riana love_for_u Data 17 februarie 2007 12:50:29
Problema Adapost Scor 12
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.69 kb

#include<stdio.h>
#include<string.h>
#include <math.h>
#include <algorithm>
#define PB push_back
#define EPS 1e-4
#define ABS(a) ( (a) < 0 ? -(a) : (a) )
#define NMAX 801
#define INF 100000001
#define INFF 100000001.0

using namespace std;

double Dist[NMAX];

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

int P[NMAX];
int C[NMAX][NMAX], F[NMAX][NMAX], G[NMAX][NMAX];
int N, NN;
int i, j, Nr, FLX;
int l, r, c;

double Cost[NMAX][NMAX], D[NMAX];
double cost_, CST, minc, minm;

int bellford(double cst_max)
{
        int changed, i, j, k;

        for (i = 0; i <= NN + 1; i++)  D[i] = INFF, P[i] = -1;

        P[0] = -1, D[0] = 0.0, changed = 1;

        for (k = 1; k <= NN + 1 && changed; k++)
            for (i = 0 , changed = 0; i <= NN + 1; i++)
	            for (j = 1; j <= G[i][0]; j++)
				{
                    int nod = G[i][j];
					
					if ( ABS(Cost[i][nod] - cst_max) < EPS || Cost[i][nod] < cst_max) 
						if(C[i][nod] > F[i][nod] && D[i] + Cost[i][nod] < D[nod])
						{
								D[ nod ] = D[i] + Cost[i][nod];
								P[ nod ] = i;
								changed = 1;
						}
				}

        return D[NN + 1] < INFF;
}

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

void augment(double cst_max)
{
	int min, cap; 
	
	while( 1 )
	{
		if( bellford(cst_max) )
		{
				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;
				}
		
				FLX += 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++) unite(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) );
			
			Dist[++Nr] = cost_;
			
			unite(i, j, cost_, 1);
		}
		
	for (i = N + 1; i <= NN; i++) unite(i, NN + 1, 0.0, 1);
		
	sort(Dist + 1, Dist + Nr + 1);
	
	l = 1, r = Nr;
	
	minm = INFF;
	
	while (l <= r)
	{
		c = (l + r) / 2;
		
		FLX = 0;
		CST = 0.0;
		
		memset(F, 0, sizeof(F));
		
		augment(Dist[c]);
		
		if ( CST != 0.0 && FLX == N)
		{
			if (minm > Dist[c]) minm = Dist[c], minc = CST;

			r = c - 1;
		}
		else l = c + 1;
	}
	
	printf("%.5lf %.5lf\n", minm, minc);

	return 0;
}