c++&oi

usaco4.1.3

一看就是求最小环,但是构图非常恶心。按照我朴素的思维方式,想了N天N夜,想到了利用BFS(或DFS)给定点标号,然后在建边的算法。
时空复杂度理论上都是很好的。但今天一上机就怂了,因为编程复杂度太大。又思考了一段时间无解之后,我求助于NOCOW。
了解了一种把边看作点,然后给边直接连上“边”的算法。实际操作中也遇到一些困惑,这里就不提了,主要是floyd算法的细节要注意。
我对该算法的细节认识:
1.k在外循环,只有前k个点是更新完的。
2.Infinity 不能取太大,会爆的。
具体的注释在代码中了

代码

关于代码最后输出 显然的结论的说明:
在一个环中,每条边经过一次,且首尾相接。
这个环上的“边”连接这图中的边集中的两个边,
且每条边恰好被连接两次.故ans要/2

posted on 2011-12-10 16:49 zyn.cpp 阅读(156) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年5月>
293012345
6789101112
13141516171819
20212223242526
272829303112
3456789

导航

统计

常用链接

留言簿

随笔档案(57)

文章档案(13)

搜索

最新评论

阅读排行榜

评论排行榜