Felicia

2007年9月28日

[计算几何]pku3391
     摘要: 问题是求平面欧几里德最小生成树的第n - k小边。
平面欧几里德最小生成树是经典问题，可以做到O(nlogn)。具体做法是先对平面点进行三角剖分，时间复杂度是O(nlogn)，三角剖分的边就是可能的在最小生成树的边。因为是平面图，所以有O(n)条边，在其上应用 Kruscal 算法即可。

  阅读全文
posted @ 2007-09-28 20:17 Felicia 阅读(777) | 评论 (0) | 编辑 收藏
 
Powered by:
C++博客
Copyright © Felicia