给定一个源节点 S， 一个汇节点 T，以及两个表示图的矩阵 Cap[ ][ ] 和 Cost[ ][ ]。其中，Cap[i][j] 是从节点 i 到节点 j 的有向边的容量，而 cost[i][j] 是从节点 i 到节点 j 沿有向边发送单位流的成本。我们的任务是从给定的图中找到一个具有最小费用最大流的可行流。
> 最小费用最大流： 从给定图中输送尽可能最大的流量所需的最小成本（每单位流）。
示例：
> 输入： S = 0, T = 4, cap[ ][ ] = {{0, 3, 4, 5, 0}, {0, 0, 2, 0, 0}, {0, 0, 0, 4, 1}, {0, 0, 0, 0, 10}, {0, 0, 0, 0, 0}},
> cost[ ][ ] = {{0, 1, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}}
> 输出： 10 1
> 解释：
> 对于给定的图，最大流 = 10，最小费用 = 1。
>
>
>
> 输入： S = 0, T = 4, cost[][] = { { 0, 1, 0, 0, 2 }, { 0, 0, 0, 3, 0 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 1 }, { 0, 0, 0, 0, 0 } }
> cap[][] = { { 0, 3, 1, 0, 3 }, { 0, 0, 2, 0, 0 }, { 0, 0, 0, 1, 6 }, { 0, 0, 0, 0, 2 }, { 0, 0, 0, 0, 0 } }
> 输出： 6 8
解决思路：
成本网络中的负环是指环路中所有边的成本之和为负的环。我们可以使用 Bellman Ford 算法 来检测它们。必须消除这些负环，因为在实际应用中，不允许流量通过这样的循环。考虑一个 负费用环，如果所有流量都必须通过这个环，那么每完成一个循环，总成本就会不断降低。为了 最小化总成本，这将导致一个无限循环。因此，每当成本网络包含负环时，这意味着成本还可以进一步降低（通过流经环的另一侧，而不是当前考虑的一侧）。一旦检测到负环，就会通过让 瓶颈容量#:~:text=In%20production%20and%20project%20management, customers%2C%20and%20low%20employee%20morale.) 的流量通过环中的所有边来将其消除。
现在，让我们来看看什么是供应节点和需求节点：
> 供应节点： 这些是添加到流中的正节点，它们产生流量。
> 需求节点： 这些是从流中减去的负节点。
> 每个节点的供应（或需求） = 流出节点的总流量 – 流入节点的总流量
我们通过向环路中的所有边发送瓶颈容量来处理负环，从而解决给定的问题。此外，由于涉及需求节点，我们会调用 Bellman Ford 算法。
请按照以下步骤解决问题：
- 将 边的容量 和 边的成本 存储在两个独立的数组中。
- 给定源节点 S 和汇节点 T，选取的边 pi，需求节点 da 以及节点之间的距离 dist，搜索是否存在从 S 到 T 的流。
- 如果流存在，则计算距离，value = dist + pi – pi[k] – cost[k]。
- 将 dist[ ] 中的距离值与 value 进行比较，并持续更新直到获得 最小流。
下面是上述方法的实现：
C++
#include
#include
#include
using namespace std;
// Stores the found edges
vector found;
// Stores the number of nodes
int N = 0;
// Stores the capacity of each edge
vector<vector> cap;
vector<vector> flow;
// Stores the cost per unit flow of each edge
vector<vector> cost;
// Stores the distance from each node
// and picked edges for each node
vector dad, dist, pi;
const int INF = INT_MAX / 2 – 1;
// Function to check if it is possible to
// have a flow from the src to sink
bool search(int src, int sink) {
// Initialise found[] to false
found = vector(N, false);
// Initialise the dist[] to INF
dist = vector(N + 1, INF);
// Distance from the source node
dist[src] = 0;
// Iterate until src reaches N
while (src != N) {
int best = N;
found[src] = true;
for (int k = 0; k < N; k++) {
// If already found
if (found[k])
continue;
// Evaluate while flow
// is still in supply
if (flow[k][src] != 0) {
// Obtain the total value
int val = dist[src] + pi[src] – pi[k] – cost[k][src];
// If dist[k] is > minimum value
if (dist[k] > val) {
// Update
dis