首页 > 代码库 > 图论算法》关于最大流转最短路两三事
图论算法》关于最大流转最短路两三事
又要来一篇高质量的博客了
这道题可以用BZOJ1001做例子,
首先我们来张图
这张图有6个点,10条边,每条边都有边权。
那么什么叫最大流最小割捏?
解释如下
在一个平面图中,能够从其实点到达终点的最大流量,等于,如果从网络中移除就能够导致网络流中断的边的集合的最小容量和。
那么这个问题如何转变为最短路问题捏
再来一张图
这张图和上图的区别就在于,我们新建了两条边,一条是从作为起源点的1向无限左建边,一条是从作为终止点的6向无限右建边。
我们又新建了7个点分别为0到6,每个点的定义为被原来的边切分出来的小区域
然后以前的每条边被重新定义为 链接 新建的 与这条边相邻的两点
所以这张图就成了这样
每条边的边权就是与当前边相切的边的权值
然后我们就会发现,这张图的 最小割 就是 新建的图 的起始点到终点的 单源最短路
然后我们裸裸的SPFA或者tarjan就好了呀。
分享例题链接:http://www.cnblogs.com/PencilWang/p/5874536.html
图论算法》关于最大流转最短路两三事
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。