图论-网络流⑥-费用流①

上一篇：图论-网络流⑤-最大流解题②

下一篇：未完待续

参考文献：

暂无

大纲

• 什么是网络流
• 最大流（最小割）

• $Dinic$Dinic （常用）
• $EK$EK
• $Sap$Sap
• $Ford-Fulkerson$Ford−Fulkerson（不讲）
• $HLPP$HLPP （快）

• 最大流解题
• 费用流 $\color{#33cc00}\texttt{Start}$Start

• $Spfa$Spfa 费用流
• $Bellman-Ford$Bellman−Ford 费用流
• $Dijkstra$Dijkstra 费用流
• $zkw$zkw 费用流 $\color{red}\texttt{End}$End
• 费用流解题

• 有上下界的网络流

• 无源汇上下界可行流
• 有源汇上下界可行流
• 有源汇上下界最大流
• 有源汇上下界最小流
• 最大权闭合子图

• 有上下界的网络流解题

上篇讲完了网络最大流的解题，如果你去找个题库刷刷，你会发现网络最大流根本不能满足我们的解题需要。面对更为复杂的情况，需要这一篇的主角出场——网络费用流。

费用流

首先讲讲费用流图。这种网络流图每条边比普通的网络流图多一个限制，就是 $cost$cost，表示这条边上每走过 $1$1 流量就要付费 $cost$cost。 如下：

最小费用最大流（就是俗称的费用流），就是求在最大流的情况下的最小费用。常见的算法是$EK$EK、最短路$+Dfs$+Dfs和$zkw$zkw费用流。

未完待续