显示标签为“Prim”的博文。显示所有博文
显示标签为“Prim”的博文。显示所有博文

2008年7月27日星期日

ZJU/ZOJ 1914 Arctic Network 解题报告

题目大意是要将p个点连接，可以对其中s段免去距离，求免去距离后最长的一段最小的距离。

很明显的最小生成树模型，用Prim算法求一次最小生成树，然后求倒数第p-s-1段的距离就是了。注意在Prim算法的更新过程中不要像Dijkstra那样更新已经judge过的点的距离，否则会造成匹配错误。

3009338 2008-07-27 20:27:17 Accepted 1914 FPC 00:00.05 1388K IwfWcf@LZOI

发帖者 IwfWcf 时间： 20:41:00 5 评论
标签： , ,
订阅： 博文 (Atom)
 
Creative Commons License
除非另有声明，本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 许可协议授权。