费用流算法

❶ 网络N中的一个s-t流f是最小费用流，当且仅当N(f)中没有负费用的有向圈。

【答案】：原始对偶算法告诉我们，流f是最优的，当且仅当(DRP)的最优解的费用为零，它等价于N'(f)中没有负费用的环流。而N'(f)中没有负费用的环流，当且仅当它没有负费用的有向圈。
综上所述，圈算法是从任意一个值为v₀的可行流f开始，利用Floyd-Warshall算法，搜索N'(f)中的负费用有向圈，在这个负费用有向圈上找出最大的环流W，则f+W仍是值为v₀的可行流，而费用却减少了。因此，圈算法保持问题(D)是可行的，故也称问题一可行算法。

❷ 网络流最小费用最大流

网络流问题中，最小费用最大流问题通过Ford和Fulkerson迭加算法来求解。基本思路是将单位流量的费用视为长度，首先通过求解最短路问题找到一条自V1至Vn的路径，将其作为可扩充路，然后使用最大流方法将其流量增至最大值。每一步迭代中，都要更新路径上的费用，直至达到最小费用最大流的状态。

迭加算法的步骤包括：给定目标流量或无限大，初始化最小费用流为零。若达到目标流量，算法结束；否则寻找从Vs到Vt的最小费用有向路，增加流量并调整费用，重复此过程，直到无最小费用有向路，最终计算出最小费用。例如，通过迭代过程，图(h)的最小费用为38，图(g)的最大流为5。

另一种求解方法是圈算法，利用Ford和Fulkerson标号算法找出流量为F（小于或等于最大流）的流f，构造调整容量流网络，搜索负费用有向图，找到最大循环流并加入原网络。在图(b)中，最小费用为38，最大流为5。

最后，ZKW费用流算法是一个优化版本，由ZKW大牛提出，它在寻找增广路的过程中，采用了KM算法的调整思想，减少了计算次数。算法首先初始化dis数组，然后进行深度优先搜索，若到达终点，更新流量并继续搜索；否则，修改dis值并判断是否结束。这种算法在处理费用流问题时，提高了效率。

网络流 network flows网络流的理论和应用在不断发展，出现了具有增益的流、多终端流、多商品流以及网络流的分解与合成等新课题。网络流的应用已遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域。

❸ 最小费用最大流问题算法举例

最小费用最大流问题的算法举例主要包括Augment Path方法和预推进算法及其变种。

1. Augment Path方法 核心思想：通过不断搜索从源点到汇点的增广路，将该路径上的容量减去最小值，并在反向路径上增加或扩大容量，以实现从源点到汇点的最大流量。 特点：确保每次操作都能增加网络中的流，从而避免陷入死循环。但在极端情况下，每次只能将流扩大1，因此效率较低，需要借助其他算法来提高效率。

2. 预推进算法 核心操作：压入和重标记。压入操作将边的始点预流尽可能多的压向终点，重标记操作将顶点的高度设为所有邻接点的高度的最小值加一。 变种： RelabeltoFront：维护一个溢出顶点的链表，通过Discharge操作不断使顶点不再溢出，直至所有顶点的高度增加。时间复杂度为O。 Highest Label Preflow Push：与RelabeltoFront本质上没有区别，但每次前移的都是高度最高的顶点，复杂度为O。 优化：Gap Heuristic，该优化在存在整数k时，对所有满足h[v]=k的顶点进行更新，以提高算法性能。

3. 算法应用 在经济学和管理学中，最小费用最大流问题用于寻找在给定容量和费用限制下，如何选择路径和分配流量以达到费用最小的要求。例如，n辆卡车从A地到B地运送物品，每条路段有不同的路费和容量限制，最小费用最大流问题即指如何分配卡车的出发路径以达到费用最低，同时确保物品全部送到。