A Za, A Za, Fighting...

坚信：勤能补拙

PKU 2421 Constructing Roads

问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2421

思路:
非常类似于PKU 2485 Highways
区别在于: "there are already some roads between some villages"
如何在求最小生成树的算法中体现某些路径已经存在了呢？
对于Prim算法，只要将已经存在的路径(u, v)的权重设置为0即可（为什么？）
对于Kruskal算法，比较容易理解，只要将已经存在的路径(u, v)进行Union操作即可，即将u, v看作是一个连通域

posted on 2010-09-05 19:58 simplyzhao 阅读(190) 评论(0) 编辑收藏引用所属分类: F_图算法

只有注册用户登录后才能发表评论。


相关文章: PKU 2060 Taxi Cab Scheme PKU 2536 Gopher II PKU 1273 Drainage Ditches PKU 1201 Intervals PKU 1125 Stockbroker Grapevine PKU 1511 Invitation Cards PKU 3463 Sightseeing PKU 2263 Heavy Cargo PKU 1158 Traffic Lights PKU 3259 Wormholes

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

A Za, A Za, Fighting...

PKU 2421 Constructing Roads

导航

统计

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜