277E - Binary Tree on Plane - CodeForces Solution

// Problem: E. Binary Tree on Plane
// Contest: Codeforces - Codeforces Round 170 (Div. 1)
// Author: wsc2008qwq
// URL: https://codeforces.com/problemset/problem/277/E
// Memory Limit: 256 MB
// Time Limit: 3000 ms

#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
void write(ll x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
const ll N=1e3+5,M=3e5+5,INF=1e15;
ll n,m,s,t,tot=1,hd[N],in[N],pre_p[N],pre_e[N],flow[N],x[N],y[N],mxf;
ld d[N],mnc;
struct Edg{
	ll to,nxt,f;
	ld c;
}es[M<<1];
void adde(ll x,ll y,ll f,ld c){
	es[++tot]=(Edg){y,hd[x],f,c};
	hd[x]=tot;
	es[++tot]=(Edg){x,hd[y],0,-c};
	hd[y]=tot; 
}
bool spfa(){
	rep(i,0,t)d[i]=INF;
	memset(flow,0x7f,sizeof(flow));
	queue<ll>q;
	q.push(s);
	d[s]=0,in[s]=1;
	pre_p[t]=-1,flow[s]=INF;
	while(!q.empty()){
		ll u=q.front();q.pop();
		in[u]=0;
		for(ll i=hd[u];i;i=es[i].nxt){
			ll v=es[i].to;
			if(es[i].f>0&&d[v]>d[u]+es[i].c){
				d[v]=d[u]+es[i].c;
				pre_p[v]=u,pre_e[v]=i;
				flow[v]=min(flow[u],es[i].f);
				if(!in[v])in[v]=1,q.push(v);
			}
		}
	}
	return pre_p[t]!=-1; 
}
void runflow(){
	for(ll x=t;spfa();){
		for(;x!=s;x=pre_p[x]){
			es[pre_e[x]].f-=flow[t];
			es[pre_e[x]^1].f+=flow[t];
		}
		mxf+=flow[t];
		mnc+=flow[t]*d[t];
		x=t;
	} 
}
ld dis(ll a,ll b){
	return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
int main(){
	n=read();
	rep(i,1,n)x[i]=read(),y[i]=read();
	s=0,t=2*n+1;
	rep(i,1,n)adde(s,i,2,0),adde(i+n,t,1,0);
	rep(i,1,n){
		rep(j,1,n){
			if(y[i]>y[j])adde(i,j+n,1,dis(i,j));
		}
	}
	runflow();
	if(mxf!=n-1)puts("-1");
	else cout<<fixed<<setprecision(12)<<mnc;
	return 0;
}