Just a Blog

前言

当初刚开始学OI的时候,对各种奇怪的中高级算法抱有极大的兴趣(结果自然是看不懂-_-),网络流则是排在前列的几大算法之一(话说我是如何在连建图和SPFA都搞不明白的情况下看进去的…)。

如今过了一年(技术还是没有什么长进,该不会的还是不会),重新看了一篇网络流与费用流,似乎。。。有那么一点理解了,谨以此文,来表达我对网络流的一点看法。

什么是网络流?

“网络流(network-flows)是一种类比水流的解决问题方法,与线性规划密切相关。”(来自百度百科)

举个例子,从某地要向某地输水,中间有许多粗细不同的管子,网络流算法解决的就是利用这些管子怎样使单位时间总输送量最大化的问题。