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