比赛 HAOI2009 模拟试题3 评测结果 ATWWWTTTTT
题目名称 公路修建 最终得分 10
用户昵称 BYVoid 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2009-04-23 11:30:26
显示代码纯文本
  1. /*
  2. * Problem: HAOI2009 模拟3 roadz
  3. * Author: Guo Jiabao
  4. * Time: 2009.4.23 10:10
  5. * State: uns
  6. * Memo: 左偏树
  7. */
  8. #include <iostream>
  9. #include <cstdio>
  10. #include <cstdlib>
  11. #include <cmath>
  12. #include <cstring>
  13. const int MAXN=5001,MAXM=MAXN*MAXN*2;
  14. using namespace std;
  15. struct edge
  16. {
  17. edge *next;
  18. int t;
  19. double w;
  20. }*V[MAXN],ES2[MAXN],*SCE[MAXN];
  21. struct LeftistHeap
  22. {
  23. struct LH_Node
  24. {
  25. LH_Node *left,*right;
  26. int NPL;
  27. edge *key;
  28. inline int LN() {return left?left->NPL:-1;}
  29. inline int RN() {return right?right->NPL:-1;}
  30. LH_Node(edge *tk):key(tk)
  31. {
  32. left=right=0;NPL=0;
  33. }
  34. }*root;
  35. LeftistHeap():root(0){}
  36. void LH_Swap(LH_Node *&a,LH_Node *&b)
  37. {
  38. LH_Node *c=a; a=b; b=c;
  39. }
  40. LH_Node* Merge(LH_Node *a,LH_Node *b)
  41. {
  42. if (!a) return b;
  43. if (!b) return a;
  44. if (a->key->w > b->key->w)
  45. LH_Swap(a,b);
  46. a->right=Merge(a->right,b);
  47. if (a->RN() > a->LN())
  48. LH_Swap(a->left,a->right);
  49. a->NPL=a->RN() + 1;
  50. return a;
  51. }
  52. void Insert(edge *k)
  53. {
  54. LH_Node *b=new LH_Node(k);
  55. root=Merge(root,b);
  56. }
  57. void Delete()
  58. {
  59. LH_Node *b=Merge(root->left,root->right);
  60. delete root;
  61. root=b;
  62. }
  63. }LH[MAXN];
  64. struct point
  65. {
  66. int x,y;
  67. }P[MAXN];
  68. struct UFS
  69. {
  70. int f[MAXN],N;
  71. void initialize(int tn)
  72. {
  73. N=tn;
  74. for (int i=1;i<=N;i++)
  75. f[i]=i;
  76. }
  77. int findroot(int a)
  78. {
  79. int r=a,t;
  80. while (f[r]!=r) r=f[r];
  81. while (f[a]!=r)
  82. {
  83. t=f[a];
  84. f[a]=r;
  85. a=t;
  86. }
  87. return r;
  88. }
  89. }U;
  90. double Ans=0;
  91. int N,LC,NewLC,EC,EC2,Dindex,Bcnt,Stop;
  92. int List[MAXN],Stack[MAXN],Low[MAXN],DFN[MAXN],Bel[MAXN];
  93. bool instack[MAXN],ava[MAXN];
  94. void tarjan(int i)
  95. {
  96. int j;
  97. Low[i]=DFN[i]=++Dindex;
  98. Stack[++Stop]=i;
  99. instack[i]=true;
  100. for (edge *e=V[i];e;e=e->next)
  101. {
  102. j=e->t;
  103. if (!DFN[j])
  104. {
  105. tarjan(j);
  106. if (Low[j] < Low[i])
  107. Low[i] = Low[j];
  108. }
  109. else if (instack[j] && DFN[j] < Low[i])
  110. Low[i] = DFN[j];
  111. }
  112. if (Low[i] == DFN[i])
  113. {
  114. Bcnt++;
  115. do{
  116. j=Stack[Stop--];
  117. instack[j]=false;
  118. Bel[j]=Bcnt;
  119. }while (j!=i);
  120. }
  121. }
  122. void SCC()
  123. {
  124. Stop=Dindex=Bcnt=0;
  125. for (int i=1;i<=N;i++)
  126. if (!Bel[i])
  127. tarjan(i);
  128. }
  129. inline double dist(point a,point b)
  130. {
  131. double x=(double)(a.x) - b.x,y=(double)(a.y) - b.y;
  132. return sqrt(x*x + y*y);
  133. }
  134. inline void addedge(int a,int b,double w)
  135. {
  136. edge *e=new edge;
  137. e->t=b; e->w=w;
  138. LH[a].Insert(e);
  139. }
  140. void init()
  141. {
  142. int i,j;
  143. freopen("roadz.in","r",stdin);
  144. freopen("roadz.out","w",stdout);
  145. scanf("%d",&N);
  146. for (i=1;i<=N;i++)
  147. {
  148. scanf("%d%d",&P[i].x,&P[i].y);
  149. List[++LC]=i;
  150. }
  151. for (i=1;i<=N;i++)
  152. for (j=1;j<=N;j++)
  153. if (i!=j)
  154. addedge(i,j,dist(P[i],P[j]));
  155. }
  156. inline void addedge2(int a,int b,double w)
  157. {
  158. ES2[++EC2].next=V[a];
  159. V[a]=ES2+EC2; V[a]->t=b; V[a]->w=w;
  160. }
  161. void makegraph()
  162. {
  163. int i,a,b;
  164. edge *e;
  165. memset(V,0,sizeof(V));
  166. for (i=1;i<=LC;i++)
  167. {
  168. a=List[i];
  169. e=LH[a].root->key;
  170. b=e->t;
  171. addedge2(a,b,e->w);
  172. }
  173. }
  174. void killshortest()
  175. {
  176. int i,a,b;
  177. edge *e;
  178. memset(SCE,0,sizeof(SCE));
  179. for (i=1;i<=LC;i++)
  180. {
  181. a=List[i];
  182. for (e=V[a];e;e=e->next)
  183. {
  184. b=e->t;
  185. if (Bel[a]==Bel[b] && (SCE[Bel[a]]==0 || e->w < SCE[Bel[a]]->w))
  186. SCE[Bel[a]] = e;
  187. }
  188. }
  189. for (i=1;i<=Bcnt;i++)
  190. if (SCE[i])
  191. SCE[i]->t=0;
  192. }
  193. void merge()
  194. {
  195. int i,a,b;
  196. U.initialize(LC);
  197. for (i=1;i<=EC2;i++)
  198. {
  199. if (ES2[i].t==0) continue;
  200. a=U.findroot(i);
  201. b=U.findroot(ES2[i].t);
  202. if (a==b) continue;
  203. U.f[b]=a;
  204. Ans += ES2[i].w;
  205. LH[a].Merge(LH[a].root,LH[b].root);
  206. }
  207. memset(ava,0,sizeof(ava));
  208. for (i=1;i<=LC;i++)
  209. ava[U.findroot(i)]=true;
  210. NewLC=0;
  211. for (i=1;i<=LC;i++)
  212. if (ava[i])
  213. List[++NewLC]=i;
  214. LC=NewLC;
  215. }
  216. void solve()
  217. {
  218. while (LC>1)
  219. {
  220. EC2=0;
  221. makegraph();
  222. SCC();
  223. killshortest();
  224. merge();
  225. }
  226. }
  227. int main()
  228. {
  229. init();
  230. solve();
  231. printf("%.2lf\n",Ans);
  232. return 0;
  233. }