记录编号	377629	评测结果	AAAAAAAAAA
题目名称	南极科考旅行	最终得分	100
用户昵称	苦读依旧	是否通过	通过
代码语言	C++	运行时间	0.725 s
提交时间	2017-03-01 19:26:08	内存使用	32.52 MiB

#include<iostream>
#include<cstdio>
#include<queue> 
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF=1000000000;
struct q{
int from;
int to;
int next;
int cap;
int flow;
double cost;
} e[1200000];
int head[12000];
int cur[12000];
bool inq[12000];
int dep[12000];
queue<int> qv;
int tt=0;
int tot=-1;
void insert(int x,int y,int flow,double cost)
{
	++tot; e[tot].from=x; e[tot].to=y; e[tot].cap=flow;
	e[tot].flow=0; e[tot].next=head[x]; e[tot].cost=cost; head[x]=tot; 
}
struct E{
int x,y;
} t[310];
double dis[610];
int a[610];
int pre[610];
int cmp(const E a,const E b)
{
	if(a.x<b.x) return 1;
	else return 0;
}
double ds(int x,int y)
{
	return sqrt((t[x].x-t[y].x)*(t[x].x-t[y].x)+(t[x].y-t[y].y)*(t[x].y-t[y].y));
}
bool SPFA(int s,int t,double &cost,int &flow)
{
	memset(inq,0,sizeof(inq));
	memset(a,0,sizeof(a));
	for(int i=0;i<=tt;++i) dis[i]=(double)INF*100;
	while(!qv.empty()) qv.pop();
	qv.push(s); inq[s]=1; dis[s]=0; a[s]=INF;
	while(!qv.empty()) {
		int x=qv.front();
		qv.pop(); inq[x]=0;
		for(int i=head[x];i!=-1;i=e[i].next) {
			if(e[i].cap>e[i].flow&&dis[e[i].to]>dis[x]+e[i].cost) {
				a[e[i].to]=min(a[x],e[i].cap-e[i].flow);
				pre[e[i].to]=i;
				dis[e[i].to]=dis[x]+e[i].cost;
				if(!inq[e[i].to]) {
					qv.push(e[i].to); inq[e[i].to]=1;
				}
			}
		}
	}
	if(dis[t]==(double)INF*100) return false;
	flow+=a[t]; cost+=a[t]*dis[t];
	int q=t;
	while(q) {
		e[pre[q]].flow+=a[t];
		e[pre[q]^1].flow-=a[t];
		q=e[pre[q]].from;
	}
	return true;
}
void maxcost(int s,int t,double &cost,int &flow)
{
	while(SPFA(s,t,cost,flow));
	return;
}
int main()
{
	freopen("BitonicTour.in","r",stdin);
	freopen("BitonicTour.out","w",stdout);
	memset(head,-1,sizeof(head));
	int n; scanf("%d",&n);
	for(int i=1;i<=n;++i) {
		int x,y; scanf("%d%d",&x,&y);
		t[i].x=x; t[i].y=y;
	}
	sort(t+1,t+n+1,cmp);
	int s=0; int t=n;
	insert(s,1,2,0); insert(1,s,0,0);
	insert(1,n+1,2,-INF); insert(n+1,1,0,INF);
	for(int i=1;i<=n-1;++i) {
		if(i!=1) insert(i,i+n,1,-INF),insert(i+n,i,0,INF);
		for(int j=i+1;j<=n;++j) {
			insert(n+i,j,1,ds(i,j)); insert(j,n+i,0,-ds(i,j));
		}
	}
	tt=n*2;
	double cost=n*(double)INF; int flow=0;
	maxcost(s,t,cost,flow);
	printf("%.2lf\n",cost);
	return 0;
}