Cod sursa(job #711138)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 11 martie 2012 14:11:26
Problema Adapost Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
#define punct pair <double, double>
#define nmax 410
#define lmax 810
#define eps 0.001
#define x first
#define y second
#define inf 1<<30

punct s[nmax], a[nmax];
vector <int> g[lmax];
queue <int> q;
double cost[lmax][lmax], ans, smin, sum, d[lmax];
int n, c[lmax][lmax], f[lmax][lmax], u[lmax], t[lmax], src, dst;

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

void graph (double cmax)
{
	int i, j;
	for (i=0; i<=dst; i++) g[i].erase(g[i].begin(), g[i].end());
	for (i=1; i<=n; i++) 
	{
		g[src].push_back (i);
		g[i].push_back (src);
		c[src][i]=1;
	}
	for (i=1; i<=n; i++)
	{
		g[n+i].push_back (dst);
		g[dst].push_back (n+i);
		c[n+i][dst]=1;
	}
	for (i=1; i<=n; i++) 
		for (j=n+1; j<dst; j++)
			if (cost[i][j]<=cmax)
			{
				g[i].push_back (j);
				g[j].push_back (i);
				c[i][j]=1;
			}
}

double bellman_ford()
{
	int i, nod, vec, j;
	for (i=0; i<=dst; i++) d[i]=inf;
	q.push (src);
	d[src] = 0;
	u[src] = 1;
	while (!q.empty())
	{
		nod = q.front();
		q.pop();
		u[nod] = 0;
		for (i=0; i<g[nod].size(); i++)
		{
			vec = g[nod][i];
			if (f[nod][vec] != c[nod][vec])
				if (cost[nod][vec] + d[nod] < d[vec])
				{
					d[vec] = cost[nod][vec] + d[nod];
					t[vec] = nod;
					if (!u[vec])
					{
						q.push(vec);
						u[vec]=1;
					}
				}
		}
	}
	return d[dst];
}


int cuplaj (double cmax)
{
	int fm, nod, cnt=0, i, j;
	for (i=0; i<=dst; i++)
	{
		t[i]=u[i]=0;
		for (j=0; j<=dst; j++) f[i][j]=c[i][j]=0;
	}
	graph (cmax);
	double x;
	sum = 0;
	while ((x = bellman_ford()) != inf)
	{
		fm = 10;
		nod = dst;
		while (nod)
		{
			fm = min (fm, c[t[nod]][nod] - f[t[nod]][nod]);
			nod = t[nod];
		}
		nod = dst;
		while (nod)
		{
			f[t[nod]][nod] += fm;
			f[nod][t[nod]] -=fm;
			nod=t[nod];
		}
		sum += x;
		cnt += fm;
	}
	return cnt;
}
	
void search (double lo, double hi)
{
	double m;
	while (lo+eps < hi)
	{
		m = (lo+hi) /2;
		if (cuplaj (m)==n)
		{
			ans = m;
			smin = sum;
			hi=m;
		} else lo=m;
	}
}

int main()
{
	freopen("adapost.in","r",stdin);
	freopen("adapost.out","w",stdout);
	scanf("%d", &n);
	int i, j;
	double x, y, dmax=0;
	for (i=1; i<=n; i++) 
	{
		scanf ("%lf %lf", &x, &y);
		s[i] = make_pair (x, y);
	}
	for (i=1; i<=n; i++)
	{
		scanf ("%lf %lf", &x, &y);
		a[i] = make_pair (x, y);
	}
	
	for (i=1; i<=n; i++)
		for (j=1; j<=n; j++) 
		{
			cost[i][n+j] = dist (s[i], a[j]);
			cost[n+j][i] = - cost[i][n+j];
			if (cost[i][n+j] > dmax) dmax=cost[i][n+j];
		}
		
	src=0;
	dst=n+n+1;
	
	search (0, dmax);
	printf ("%lf %lf\n", ans, smin);
}