比赛 HAOI2009 模拟试题3 评测结果 ATWWWTTTTT
题目名称 公路修建 最终得分 10
用户昵称 BYVoid 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2009-04-23 11:30:26
显示代码纯文本
/* 
 * Problem: HAOI2009 模拟3 roadz
 * Author: Guo Jiabao
 * Time: 2009.4.23 10:10
 * State: uns
 * Memo: 左偏树
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=5001,MAXM=MAXN*MAXN*2;
using namespace std;
struct edge
{
	edge *next;
	int t;
	double w;
}*V[MAXN],ES2[MAXN],*SCE[MAXN];
struct LeftistHeap
{
	struct LH_Node
	{
		LH_Node *left,*right;
		int NPL;
		edge *key;
		inline int LN() {return left?left->NPL:-1;}
		inline int RN() {return right?right->NPL:-1;}
		LH_Node(edge *tk):key(tk)
		{
			left=right=0;NPL=0;
		}
	}*root;
	LeftistHeap():root(0){}
	void LH_Swap(LH_Node *&a,LH_Node *&b)
	{
		LH_Node *c=a; a=b; b=c;
	}
	LH_Node* Merge(LH_Node *a,LH_Node *b)
	{
		if (!a) return b;
		if (!b) return a;
		if (a->key->w > b->key->w)
			LH_Swap(a,b);
		a->right=Merge(a->right,b);
		if (a->RN() > a->LN())
			LH_Swap(a->left,a->right);
		a->NPL=a->RN() + 1;
		return a;
	}
	void Insert(edge *k)
	{
		LH_Node *b=new LH_Node(k);
		root=Merge(root,b);
	}
	void Delete()
	{
		LH_Node *b=Merge(root->left,root->right);
		delete root;
		root=b;
	}
}LH[MAXN];
struct point
{
	int x,y;
}P[MAXN];
struct UFS
{
	int f[MAXN],N;
	void initialize(int tn)
	{
		N=tn;
		for (int i=1;i<=N;i++)
			f[i]=i;
	}
	int findroot(int a)
	{
		int r=a,t;
		while (f[r]!=r) r=f[r];
		while (f[a]!=r)
		{
			t=f[a];
			f[a]=r;
			a=t;
		}
		return r;
	}
}U;
double Ans=0;
int N,LC,NewLC,EC,EC2,Dindex,Bcnt,Stop;
int List[MAXN],Stack[MAXN],Low[MAXN],DFN[MAXN],Bel[MAXN];
bool instack[MAXN],ava[MAXN];
void tarjan(int i)
{
	int j;
	Low[i]=DFN[i]=++Dindex;
	Stack[++Stop]=i;
	instack[i]=true;
	for (edge *e=V[i];e;e=e->next)
	{
		j=e->t;
		if (!DFN[j])
		{
			tarjan(j);
			if (Low[j] < Low[i])
				Low[i] = Low[j];
		}
		else if (instack[j] && DFN[j] < Low[i])
			Low[i] = DFN[j];
	}
	if (Low[i] == DFN[i])
	{
		Bcnt++;
		do{
			j=Stack[Stop--];
			instack[j]=false;
			Bel[j]=Bcnt;
		}while (j!=i);
	}
}
void SCC()
{
	Stop=Dindex=Bcnt=0;
	for (int i=1;i<=N;i++)
		if (!Bel[i])
			tarjan(i);
}
inline double dist(point a,point b)
{
	double x=(double)(a.x) - b.x,y=(double)(a.y) - b.y;
	return sqrt(x*x + y*y);
}
inline void addedge(int a,int b,double w)
{
	edge *e=new edge;
	e->t=b; e->w=w;
	LH[a].Insert(e);
}
void init()
{
	int i,j;
	freopen("roadz.in","r",stdin);
	freopen("roadz.out","w",stdout);
	scanf("%d",&N);
	for (i=1;i<=N;i++)
	{
		scanf("%d%d",&P[i].x,&P[i].y);
		List[++LC]=i;
	}
	for (i=1;i<=N;i++)
		for (j=1;j<=N;j++)
			if (i!=j)
				addedge(i,j,dist(P[i],P[j]));
}
inline void addedge2(int a,int b,double w)
{
	ES2[++EC2].next=V[a];
	V[a]=ES2+EC2; V[a]->t=b; V[a]->w=w;
}
void makegraph()
{
	int i,a,b;
	edge *e;
	memset(V,0,sizeof(V));
	for (i=1;i<=LC;i++)
	{
		a=List[i];
		e=LH[a].root->key;
		b=e->t;
		addedge2(a,b,e->w);
	}
}
void killshortest()
{
	int i,a,b;
	edge *e;
	memset(SCE,0,sizeof(SCE));
	for (i=1;i<=LC;i++)
	{
		a=List[i];
		for (e=V[a];e;e=e->next)
		{
			b=e->t;
			if (Bel[a]==Bel[b] && (SCE[Bel[a]]==0 || e->w < SCE[Bel[a]]->w))
				SCE[Bel[a]] = e;
		}
	}
	for (i=1;i<=Bcnt;i++)
		if (SCE[i])
			SCE[i]->t=0;
}
void merge()
{
	int i,a,b;
	U.initialize(LC);
	for (i=1;i<=EC2;i++)
	{
		if (ES2[i].t==0) continue;
		a=U.findroot(i);
		b=U.findroot(ES2[i].t);
		if (a==b) continue;
		U.f[b]=a;
		Ans += ES2[i].w;
		LH[a].Merge(LH[a].root,LH[b].root);
	}
	memset(ava,0,sizeof(ava));
	for (i=1;i<=LC;i++)
		ava[U.findroot(i)]=true;
	NewLC=0;
	for (i=1;i<=LC;i++)
		if (ava[i])
			List[++NewLC]=i;
	LC=NewLC;
}
void solve()
{
	while (LC>1)
	{
		EC2=0;
		makegraph();
		SCC();
		killshortest();
		merge();
	}
}
int main()
{
	init();
	solve();
	printf("%.2lf\n",Ans);
	return 0;
}