本文主要是介绍【算法导论】第二十六章最大流，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一，概念
1）流网络：简单有向图，且有两个特别的顶点（源点s，汇点t）
2）流的边标识为f(u,v)/c(u,v)，流量/容量
3）流的三个性质：1>容量限制 对于所有边 流量<容量
2>反对称性 f(u,v)=-f(v,u)
3>流守恒性 正向流与反响流之和为零
4）割：流网络G=(V,E)的割（S,T）将顶点V划分为S和T=V-S两部分，定义割的容量为C(S)割这条线上S中顶点到T中顶点的容量之和
5）残留网络： 残留容量 c f (u, v) = c(u, v) - f (u, v) //边的容量减去边的实际流量
6）增广路径：对于残留网络 G f 中的一条 s-t 路径 p 称其为增广路径
二，最大流和最小割问题
1）最大流：对于一个流网络 G (V , E ) ,其流量 f 的最大值称为最大流,最大流问题就
是求一个流网络的最大流。
2）最小割：是指流网络中容量最小的割
三、最大流算法的应用
1）最大流模型
例题：现在有 N 只奶牛,F 种食物和 D 种饮料,每只奶牛喜欢其中的一些食物和饮料。现在每种食物和饮料只能分给一只奶牛,每只奶牛也只能吃一种食物和一种饮料,问最多能使多少奶牛既吃到食物又喝到饮料。
解决：由于有 N 只奶牛、F 种食物和 D 种饮料,因此我们可以将这些东西抽象成图中的点。为了方便,我们将食物放在左边,奶牛放在中间,饮料放在右边。由于食物和饮料的使用限制,我们从源点向每种食物连一条边,从每种饮料向汇点连一条边,容量都为 1。而每只奶牛都有喜欢的食物和饮料,因此将每只奶牛喜欢的食物连到这只奶牛,从这只奶牛连到每种它喜欢的饮料。但这样是否就对了呢?实际还是有问题的,因为经过每只奶牛的食物可能超过一种,这就意味着每只奶牛可能会吃超过一组的食物和饮料,而这在题目中是不允许的。怎么解决这个问题呢?我们又回到了流的基本性质:容量限制f (u, v) - c(u, v) 。因此我们将每只奶牛拆成两个点,同一只奶牛的两个点之间连边,容量为 1。这样们就能保证通过每只奶牛的流量为 1 了。每个流对应每种方案,最大流即为最佳方案。
这篇关于【算法导论】第二十六章最大流的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
