首页 > 代码库 > 图论算法》关于最大流转最短路两三事

图论算法》关于最大流转最短路两三事

  又要来一篇高质量的博客了

  这道题可以用BZOJ1001做例子,

  首先我们来张图

技术分享

这张图有6个点,10条边,每条边都有边权。

那么什么叫最大流最小割捏?

解释如下

在一个平面图中,能够从其实点到达终点的最大流量,等于,如果从网络中移除就能够导致网络流中断的边的集合的最小容量和。

那么这个问题如何转变为最短路问题捏

再来一张图

技术分享

这张图和上图的区别就在于,我们新建了两条边,一条是从作为起源点的1向无限左建边,一条是从作为终止点的6向无限右建边。

我们又新建了7个点分别为0到6,每个点的定义为被原来的边切分出来的小区域

然后以前的每条边被重新定义为  链接 新建的  与这条边相邻的两点 

所以这张图就成了这样

技术分享

 

每条边的边权就是与当前边相切的边的权值

然后我们就会发现,这张图的  最小割  就是  新建的图  的起始点到终点的  单源最短路

然后我们裸裸的SPFA或者tarjan就好了呀。

分享例题链接:http://www.cnblogs.com/PencilWang/p/5874536.html

图论算法》关于最大流转最短路两三事