Cod sursa(job #711155)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 11 martie 2012 14:41:24
Problema Adapost Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.48 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
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], b[nmax*nmax];
int n, c[lmax][lmax], f[lmax][lmax], u[lmax], t[lmax], src, dst, h, r[nmax], cnt;

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_cost (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;
}

int pair_up (int nod)
{
	if (u[nod]==cnt) return 0;
	int i, v;
	u[nod]=cnt;
	for (i=0; i<g[nod].size(); i++)
	{
		v=g[nod][i];
		if (t[v]==-1 || pair_up(t[v]))
		{
			t[v]=nod;
			r[nod]=v;
			return 1;
			
		}
	}
	return 0;
}

int cuplaj(double cmax)
{
	int i, j, sum=0, last=-1;
	for (i=1; i<=n; i++)
	{
		t[i]=-1;
		r[i]=u[i]=0;
	}
	for (i=1; i<=n; i++) g[i].erase (g[i].begin(), g[i].end());
	for (i=1; i<=n; i++)
		for (j=n+1; j<dst; j++) 
			if (cost[i][j] <= cmax) g[i].push_back(j-n);
	
	cnt=0;
	while (sum != last)
	{
		last=sum;
		cnt++;
		for (i=1; i<=n; i++)
			if (!r[i]) sum+=pair_up (i);
	}
	return sum;
}
	
void search (int lo, int hi)
{
	int m;
	while (lo<= hi)
	{
		m = (lo+hi) /2;
		if (cuplaj (b[m])==n)
		{
			ans = b[m];
			hi=m-1;
		} else lo=m+1;
	}
}

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]);
			b[++h]=cost[i][n+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;
	
	sort (b+1, b+h+1);
	search (1, h);
	cuplaj_cost(ans);
	printf ("%lf %lf\n", ans, sum);
}