c++&oi

USACO5两道图论

先写一道,USACO5.4.5telecow求图的最小点割,运用拆点法(同求图的最小路径覆盖),然后求最小割。
我采用了一种流量*6000+序号i的方法,但好像有问题,如果真的要写的话就像上面一道最小割一样在DFS一下。
说明:两种搜索
         1.论文中的floodfill(BFS/DFS)求该最大流的最小割。
         2.DFS枚举割点,求最大流为0,表示s->t不通(或直接BFS验证不通)。
不知对不对的代码

另一道是5.3.3schlnet,与图的强连通分量有关。
方法实在太多了,准备一一实现后再深入总结。
1.floyd O(n^3)
2.tarjianO(m+n)
3.dfn-low O(m+n)
4.Kosaraju O((m+n)*2)
我的代码(dfn_low)

posted on 2012-04-10 15:05 zyn.cpp 阅读(183) 评论(0)  编辑 收藏 引用


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


<2012年2月>
2930311234
567891011
12131415161718
19202122232425
26272829123
45678910

导航

统计

常用链接

留言簿

随笔档案(57)

文章档案(13)

搜索

最新评论

阅读排行榜

评论排行榜