Cod sursa(job #676652)

Utilizator darkseekerBoaca Cosmin darkseeker Data 9 februarie 2012 14:27:33
Problema Adapost Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.2 kb
#include <fstream>
#include <queue>
#include <cassert>
#include <algorithm>
#include <cmath>
using namespace std;

#define NMAX 900
#define inf 10000000
#define in "adapost.in"
#define out "adapost.out"

double edges[NMAX * NMAX];
double coordX[NMAX],coordY[NMAX],sCoordX[NMAX],sCoordY[NMAX];
double Cost[NMAX][NMAX],dist[NMAX];
int G[NMAX][NMAX],F[NMAX][NMAX],C[NMAX][NMAX];
int	inQ[NMAX],t[NMAX],cntInQ[NMAX];
int s,d,N;
double minValue = inf,minFlow = inf,lim;
queue<int> Q;

inline void refresh()
{
	int i,j;
	for(i = s; i <= d; i++)
		for(j = s; j <= d; j++)
			F[i][j] = F[j][i] = 0;
}

double min(double a,double b)
{
	return (a<b)?a:b;
}

double abs1(double a)
{
	return (a>0)?a:-a;
}

inline double bellman_ford(double lim)
{
	int nod,v,i;
	double flux = inf;
	
	for(i = s; i <= d; i++)
		inQ[i] = 0,dist[i] = inf,cntInQ[i] = 0;
	
	dist[s] = 0; inQ[s] = 0; Q.push(s);
	
	while(!Q.empty())
	{
		nod = Q.front();
		Q.pop(), inQ[nod] = 0;
		
		for(i = 1; i <= G[nod][0]; i++)
		{
			v = G[nod][i];
			if((Cost[nod][v] <= lim)&&(dist[v] > dist[nod] + Cost[nod][v]) && C[nod][v] > F[nod][v])
			{
				dist[v] = dist[nod] + Cost[nod][v];
				t[v] = nod;
				if(!inQ[v])
					if(cntInQ[v] > N)
						return inf;
					else
					cntInQ[v]++,inQ[v] = 1,Q.push(v);
			}
		}
	}
	
	if(dist[d] != inf)
	{
		for(i = d; i != s; i = t[i])
			flux = min(flux,C[t[i]][i] - F[t[i]][i]);
		for(i = d; i != s; i = t[i])
			{
				F[t[i]][i] += flux;
				F[i][t[i]] -= flux;
		}
		return flux * dist[d];
	}
	
	return 0;
}

int GetCard()
{
	int i,j,card = 0;
	double max = 0;
	
	for(i = 2; i <= N + 1; i++)
		for(j = N + 2; j < d; j++)
			if(F[i][j] == 1)
				{
					card++;
					break;
				}
	return card;
}

double Flow()
{
	int card;
	
	double ans = 0,tans;
	
	do{
		tans = bellman_ford(lim);
		if(tans == inf)
			return inf;
		ans += tans;
	}while(tans > 0);
	
	card = GetCard();
	assert(card <= N);
	
	if(card < N)
		return inf;
	else
		return ans;
}

void solve()
{
	int i;
	double aux = inf;
	
	for(i = N; aux == inf; i++)
		{
			lim = edges[i];
			aux = Flow();
			refresh();
		}
	
	minFlow = aux;
	minValue = edges[i];
}

double distanta(double x,double y,double x1,double y1)
{
	return sqrt((x - x1) * (x - x1) + (y - y1) * (y - y1));
}

int main()
{
	ifstream fin(in);
	ofstream fout(out);
	
	fin>>N;
	int ind = 0,i,j,p,q;
	s = 1;
	d = 2 * N + 2;
	
	for(i = 1; i <= N; i++)
		fin>>coordX[i]>>coordY[i];
	
	for(i = 1; i <= N; i++)
		fin>>sCoordX[i]>>sCoordY[i];
	
	for(i = 1; i <= N; i++)
		for(j = 1; j <= N; j++)
			{
				edges[++ind] = distanta(coordX[i],coordY[i],sCoordX[j],sCoordY[j]);
				p = i + 1;
				q = j + N + 1;
				Cost[p][q] = edges[ind];
				Cost[q][p] = -edges[ind];
				C[p][q] = 1;
				G[p][++G[p][0]] = q;
				G[q][++G[q][0]] = p;
			}
	
	sort(edges + 1, edges + N * N + 1);
	
	for(i = 2; i <= N + 1; i++)
	{
		C[s][i] = 1;
		G[s][++G[s][0]] = i;
		G[i][++G[i][0]] = s;
	}
	
	for(i = N + 2; i <= d; i++)
	{
		G[i][++G[i][0]] = d;
		G[d][++G[d][0]] = i;
		C[i][d] = 1;
	}
	
	solve();
	
	fout<<minValue<<' '<<minFlow<<'\n';
	
	fin.close();
	fout.close();
	
	return 0;
	
}