比赛 |
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;
}