F
e
l
i
c
i
a
导航
C++博客
首页
新随笔
联系
聚合
管理
<
2007年9月
>
日
一
二
三
四
五
六
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
6
统计
随笔 - 149
文章 - 0
评论 - 315
引用 - 0
公告
访问量
定制我的博客魔方
Yodao提供
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(21)
给我留言
查看公开留言
查看私人留言
随笔分类
(145)
ACM/ICPC 纪事(13)
(rss)
Felicia 的标程(3)
(rss)
TopCoder SRM(5)
(rss)
动态规划(28)
(rss)
计算几何(52)
(rss)
图论(6)
(rss)
心情日记(33)
(rss)
杂题(5)
(rss)
随笔档案
(149)
2010年10月 (5)
2009年1月 (2)
2008年2月 (2)
2008年1月 (8)
2007年12月 (6)
2007年11月 (5)
2007年10月 (30)
2007年9月 (47)
2007年8月 (44)
相册
百度之星2007
女友Ader
校园风景
ACMers
barnabas
Codger
ecjtubaowp
Felicia's New Blog
Flyfox
Hailer
Liang
LittleKid
Nash635
Owen
Richardxx
[推荐]不可不看的超级牛的网站
updog
wywcgs
海狸鼠DLUT
农夫三拳
潘帕斯雄鹰
踏雪赤兔
巫山霏云
星丞
Pretty Girls
Ader
最新随笔
1. [导入]论函数调用约定(修订版)
2. [导入]CodeColorer的可视化插入代码
3. [导入]Gravatar头像被墙的解决方法
4. [导入]Win7下解决80端口被占用的办法
5. [导入]C# 泛型+扩展方法
6. <天龙八部Online>资源包Axp格式研究
7. 如何加载《天龙八部》Skeleton
8. 我已更换新的blog http://gccfeli.cn 此blog的文章已全部转移
9. 今天自己做果冻吃
10. 非常喜欢珞珈山水离版画面的一首诗
搜索
最新评论
1. re: [动态规划]pku1038
@Run&Run
里面的两处>?=是什么意思
--prister
2. re: USACO历年比赛题目列表,测试数据和解题报告下载[未登录]
已经打不开了
--lee
3. re: WF的T-shirt颜色选什么好呢?
我还是喜欢 gekius的t-shirt多些 gekius.com
--banyumalu
4. re: [动态规划]pku3375
求数据
--77
5. re: [动态规划]pku1141
你的这个代码提交WA了
--wwq
阅读排行榜
1. USACO历年比赛题目列表,测试数据和解题报告下载(27068)
2. [动态规划]pku 部分动态规划题目列表(6558)
3. [计算几何]两圆求交点(5806)
4. [动态规划]动态规划总结 by Amber(3929)
5. [计算几何]pku 部分计算几何题目列表(3174)
评论排行榜
1. 友情链接邀请(42)
2. USACO历年比赛题目列表,测试数据和解题报告下载(38)
3. 2007南京赛区总结 by mmd(19)
4. [动态规划]pku2411(12)
5. [计算几何]pku 部分计算几何题目列表(12)
2007年9月28日
[计算几何]pku3391
摘要: 问题是求平面欧几里德最小生成树的第n - k小边。
平面欧几里德最小生成树是经典问题,可以做到O(nlogn)。具体做法是先对平面点进行三角剖分,时间复杂度是O(nlogn),三角剖分的边就是可能的在最小生成树的边。因为是平面图,所以有O(n)条边,在其上应用 Kruscal 算法即可。
阅读全文
posted @
2007-09-28 20:17
Felicia 阅读(771) |
评论 (0)
|
编辑
收藏