图论-网络流①-什么是网络流算法

图论-网络流①-什么是网络流下一篇：图论-网络流②-最大流①
参考文献：

https://www.cnblogs.com/DuskOB/p/11216861.html

https://blog.csdn.net/yjr3426619/article/details/82808303

https://blog.csdn.net/lym940928/article/details/90209172

https://baike.baidu.com/item/%E7%BD%91%E7%BB%9C%E6%B5%81/2987528?fr=aladdin

https://www.cnblogs.com/pk28/p/8039645.html

https://blog.csdn.net/disgustinglemon/article/details/51296636

网络流是一类图论算法，同时也多用于解决应用问题，是图论转化解决问题的代表性算法。
大纲

什么是网络流Start \color{#33cc00}\texttt{Start} StartEnd \color{red}\texttt{End} End

最大流（最小割）

D i n i c Dinic Dinic （常用）

E K EK EK

S a p Sap Sap

F o r d ? F u l k e r s o n Ford-Fulkerson Ford?Fulkerson（不讲）

H L P P HLPP HLPP （快）

最大流解题

费用流

E K EK EK 费用流

D i n i c Dinic Dinic 费用流

z k w zkw zkw 费用流

费用流解题

有上下界的网络流

无源汇上下界可行流

有源汇上下界可行流

有源汇上下界最大流

有源汇上下界最小流

最大权闭合子图

有上下界的网络流解题

什么是网络流

网络流(network-flows)是一种类比水流的解决问题方法，与线性规划密切相关。网络流的理论和应用在不断发展，出现了具有增益的流、多终端流、多商品流以及网络流的分解与合成等新课题。网络流的应用已遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域。 ——百度百科

【图论-网络流①-什么是网络流】网络流图是一个有向图，不一定是有向无环图（DAG）。其中的点是网络流节点，边权是流量。大部分网络流有源点（S）和汇点（T）。如下：

文章图片

如果把网络流图比作水管道系统，那么网络流节点就是一个水库，网络流边就是管道，网络流边的边权就是管道的宽度。源点就是某个输水的大江大河，汇点就是水最终流到的地方。
如果把网络流图比作电路图，那么源点汇点就分别是电源两头，网络流边就是导线，边权就是电流。
下一篇会讲最大流定义、最小割定理以及 D i n i c Dinic Dinic算法。
祝大家学习愉快！