Cod sursa(job #323472)

Utilizator AndreyPAndrei Poenaru AndreyP Data 12 iunie 2009 10:44:43
Problema Adapost Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.05 kb
#include<stdio.h>
#include<string.h>
#include<bitset>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define N 810
short n;
const double eps=0.001;
bitset<410> viz;
short l[N],r[N];
char c[N][N],f[N][N];
double d[N],ka,smin;
short inheap[N],h[N],nh,t[N];
double caut[170000];
int cc;
vector< pair<short,double> > a[N];
inline char cmp(double x,double y)
{
	if(x+eps<y)
		return -1;
	if(y+eps<x)
		return 1;
	return 0;
}
inline double dist(pair<double,double> &x,pair<double,double> &y)
{
	return sqrt((x.fs-y.fs)*(x.fs-y.fs)+(x.sc-y.sc)*(x.sc-y.sc));
}
inline short left_son(short x)
{
	return x<<1;
}
inline short right_son(short x)
{
	return (x<<1)+1;
}
inline short father(short x)
{
	return x>>1;
}
inline void upheap(short k)
{
	short key=h[k];
	while(k>1 && cmp(d[h[father(k)]],d[key])==1)
	{
		h[k]=h[father(k)];
		inheap[h[k]]=k;
		k=father(k);
	}
	h[k]=key;
	inheap[h[k]]=k;
}
inline void downheap(short k)
{
	short son;
	do
	{
		son=0;
		if(left_son(k)<=nh)
		{
			son=left_son(k);
			if(right_son(k)<=nh && cmp(d[h[right_son(k)]],d[h[son]])==-1)
				son=right_son(k);
			if(cmp(d[h[son]],d[h[k]])!=-1)
				son=0;
		}
		if(son)
		{
			swap(h[k],h[son]);
			inheap[h[k]]=k;
			inheap[h[son]]=son;
			k=son;
		}
	}while(son);
}
inline void citire()
{
	scanf("%hd",&n);
	n<<=1;
	pair<double,double> v[N];
	a[n+1].reserve((n>>1)+2);
	for(short i=1; i<=n; ++i)
	{
		scanf("%lf%lf",&v[i].fs,&v[i].sc);
		if(i>(n>>1))
		{
			a[i].reserve((n>>1)+2);
			for(short j=1; (j<<1)<=n; ++j)
			{
				double aux=dist(v[i],v[j]);
				caut[++cc]=aux;
				a[j].pb(mp(i,aux));
				a[i].pb(mp(j,-aux));
				c[j][i]=1;
			}
			a[i].pb(mp(n+2,0));
			c[i][n+2]=1;
		}
		else
		{
			a[i].reserve((n>>1)+2);
			a[n+1].pb(mp(i,0));
			c[n+1][i]=1;
		}
	}
}
inline bool dijkstra()
{
	short n1=n+2;
	for(short i=1; i<=n1; ++i)
	{
		d[i]=3000;
		inheap[i]=0;
		t[i]=-1;
	}
	nh=1;
	d[n+1]=0;
	inheap[n+1]=1;
	h[1]=n+1;
	while(nh)
	{
		short now=h[1];
		inheap[now]=0;
		h[1]=h[nh--];
		if(nh)
		{
			inheap[h[1]]=1;
			downheap(1);
		}
		for(short i=0,lim=a[now].size(); i<lim; ++i)
		{
			short next=a[now][i].fs;
			double cost=a[now][i].sc;
			if(cmp(cost,ka)==1 || c[now][next]==f[now][next] || cmp(d[next],d[now]+cost)!=1)
				continue;
			d[next]=d[now]+cost;
			t[next]=now;
			if(inheap[next])
				upheap(inheap[next]);
			else
			{
				h[++nh]=next;
				inheap[next]=nh;
				upheap(nh);
			}
		}
	}
	if(d[n1]==3000)
		return false;
	smin+=d[n1];
	return true;
}
inline void vezi()
{
	short n1=n+2;
	short flux=0;
	while(dijkstra())
	{
		short aux=n+2;
		++flux;
		while(aux!=n+1)
		{
			++f[t[aux]][aux];
			--f[aux][t[aux]];
			aux=t[aux];
		}
	}
}
bool pairup(short nod)
{
	if(viz[nod])
		return false;
	viz[nod]=1;
	for(short i=0,lim=a[nod].size(); i<lim; ++i)
	{
		if(cmp(a[nod][i].sc,ka)!=1 && !l[a[nod][i].fs])
		{
			r[nod]=a[nod][i].fs;
			l[a[nod][i].fs]=nod;
			return true;
		}
	}
	for(short i=0,lim=a[nod].size(); i<lim; ++i)
	{
		if(cmp(a[nod][i].sc,ka)!=1 && pairup(l[a[nod][i].fs]))
		{
			r[nod]=a[nod][i].fs;
			l[a[nod][i].fs]=nod;
			return true;
		}
	}
	return false;
}
inline bool vezi1()
{
	bool change=true;
	memset(l,0,sizeof(l));
	memset(r,0,sizeof(r));
	short n1=(n>>1)+1;
	while(change)
	{
		change=false;
		viz.reset();
		for(short i=1; i<n1; ++i)
		{
			if(!r[i])
				change|=pairup(i);
		}
	}
	for(short i=1; i<n1; ++i)
	{
		if(!r[i])
			return false;
	}
	return true;
}
bool compar(const double &x,const double &y)
{
	if(cmp(x,y)==-1)
		return true;
	return false;
}
int main()
{
	freopen("adapost.in","r",stdin);
	freopen("adapost.out","w",stdout);
	citire();
	sort(caut+1,caut+cc+1,compar);
	int p=1,u=cc;
	while(p<u)
	{
		int mij=(p+u)>>1;
		ka=caut[mij];
		if(vezi1())
			u=mij;
		else
			p=mij+1;
	}
	ka=caut[p];
	vezi();
	printf("%lf %lf\n",caut[p],smin);
	return 0;
}