尧图网站建设 
文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载导读本文聚焦于 cp-algorithms 仓库中 src/graph/min_cost_flow.md 所讲解的最小费用流问题及其经典解法——逐次最短路Successive Shortest Path算法。该算法是最大流算法Edmonds-Karp在带权边费用场景下的直接推广既能求解给定流量 $K$ 的最小费用流也能通过令 $K \to \infty$ 求解最小费用最大流。读完本文你将掌握最小费用流问题的数学模型、残量网络的构造、算法的正确性前提与复杂度上界以及仓库中基于 SPFA 的完整可运行 C 实现并了解该算法在仓库内其他文档如指派问题中的应用。问题定义最小费用流与最小费用最大流给定一个由 $n$ 个顶点、$m$ 条边构成的网络 $G$。每条边通常为有向边带两个整数属性容量capacity非负整数 $U_{ij}$表示该边上可承载的流量上限费用cost整数 $C_{ij}$表示沿该边运输每单位流量的代价。同时网络中标定了源点 $s$与汇点 $t$。对于给定的目标流量值 $K$需要找到流量恰好为 $K$的可行流并且在该类流量中使总费用最低。这一问题被称为最小费用流问题minimum-cost flow problem。另一种常见表述是先求出最大流再在所有最大流中选取总费用最小的那个即最小费用最大流问题minimum-cost maximum-flow problem。两种变体都可以用逐次最短路算法统一求解——原文档指出It is not difficult to see, that if we set $K$ to infinity, then the algorithm will find the minimum-cost maximum-flow.算法总览与 Edmonds-Karp 的血缘关系逐次最短路算法与仓库中 Edmonds-Karp 最大流算法 在结构上高度相似两者都反复在残量网络中寻找一条从 $s$ 到 $t$ 的增广路并沿路径推送尽可能多的流量。唯一的关键区别在于寻路的度量标准Edmonds-Karp 用 BFS 找边数最少的增广路逐次最短路算法找费用之和最小的增广路最短路径意义上的最短。这一改动使得每轮增广得到的都是当前流下的最优边际增广从而保证了最终结果的总费用最小。最短路部分的计算可直接复用仓库中的 Bellman-Ford含其 SPFA 变体或经过势能改造的 Dijkstra。最简单情形有向图且无重边先考察最简情形图是有向的且任意一对顶点之间至多有一条边若存在 $(i,j)$则不允许同时存在 $(j,i)$。符号约定$U_{ij}$边 $(i,j)$ 的容量$C_{ij}$边 $(i,j)$ 的单位流量费用$F_{ij}$边 $(i,j)$ 上当前的流量初始全部为 $0$。构造反向边对每条边 $(i,j)$ 加入反向边$(j,i)$其容量 $U_{ji}0$、费用 $C_{ji}-C_{ij}$。由于最简情形保证 $(j,i)$ 原本不存在于网络中加入反向边后网络仍然不是多重图。算法运行全程保持对称条件$$F_{ji} -F_{ij}$$也就是说沿着反向边撤销流量等价于把正向边的流量取负号。反向边是让算法能够回收已推送流量、重新路由的关键机制——这正是流算法区别于普通贪心路径搜索的核心。残量网络对固定流 $F$定义残量网络residual network其语义与 Ford-Fulkerson 方法 中完全一致残量网络只包含未饱和的边即满足 $F_{ij} U_{ij}$ 的边每条这样的边其残量容量为$$R_{ij} U_{ij} - F_{ij}$$注意反向边同样参与残量网络的构成当正向边已有流量 $F_{ij} 0$ 时反向边 $(j,i)$ 的残量容量 $R_{ji} U_{ji} - F_{ji} 0 - (-F_{ij}) F_{ij} 0$因此它是一条可用的回退边费用为 $-C_{ij}$。这正是算法能够对已推送的流量进行重新调度的原因。逐次最短路迭代流程初始化所有流量为 $0$构建含反向边的网络在残量网络中寻找从 $s$ 到 $t$ 的费用最短路径不是边数最短若不存在这样的路径当前流量尚未达到 $K$则说明流量为 $K$ 的可行流根本不存在算法终止否则 $F$ 即为所求。若找到路径则沿路径尽可能多地增广取路径上所有边残量容量 $R_{ij}$ 的最小值作为可增广量正向边流量增加该值反向边相应减少若流量在某轮达到 $K$立即停止。需要注意最后一轮只需增广到使总流量恰好为 $K$ 的量即可代码中体现为f min(f, K - flow)不要让最终流量超过 $K$。从算法流程可以直接看出把 $K$ 设为无穷大迭代会一直持续到残量网络中 $s$ 与 $t$ 不再连通此时得到的正是最小费用最大流。无向图与多重图实现的额外考量原文档明确指出无向图或多重图在概念上与上述算法并无差别算法同样可以工作但实现会更复杂。原因是无向边的拆分。一条无向边 $(i,j)$ 等价于两条容量、费用都相同的有向边 $(i,j)$ 与 $(j,i)$。由于逐次最短路算法会为每条有向边再生成一条反向边一条无向边最终会被拆成4 条有向边网络事实上变成了多重图。多重边带来的三个实现要求每条多重边的流量必须分开存储——不能用一对顶点对应一条边的简单矩阵或邻接数组寻路时必须区分具体是哪一条边被选入路径——除常规的前驱顶点数组p[]外还必须额外记录从哪条边走过来即前驱边编号否则无法正确回溯增广路径增广后必须沿对应反向边回退——由于存在多条平行边必须为每条边显式存储其反向边的编号。除以上三点外无向图与多重图不再有其他障碍。复杂度分析理论边界与势能加速该算法在最坏情况下是指数级的每轮增广可能只推送 1 单位流量因此要得到流量大小为 $F$ 的最小费用流最坏需要 $O(F)$ 轮迭代。若每次寻路花费 $T$则总复杂度为$$O(F \cdot T)$$其中 $T$ 是从源到汇求最短路径所需时间。原文档给出了两种具体配置寻路算法单轮寻路 $T$总复杂度Bellman-Ford / SPFA$O(nm)$$O(F \cdot mn)$经势能改造的 Dijkstra堆优化初始预处理 $O(nm)$之后每轮 $O(m \log n)$$O(mn F \cdot m \log n)$后者的核心是Johnson 势能potentials思想由于残量网络中存在费用为负的反向边不能直接套用 Dijkstra需要先做一轮 Bellman-Ford 求出每个顶点的势能把负权边转化为非负权再逐轮用 Dijkstra 加速。可参考仓库中的 Dijkstra 稠密图实现 与 稀疏图堆优化实现 理解底层寻路逻辑。原文档还提到可以进一步将势能思想与Dinic 算法结合把迭代轮数从 $F$ 压缩到 $\min(F, nC)$其中 $C$ 是网络中边费用的最大值。实现基于 SPFA 的逐次最短路附完整源码原文档给出的实现针对最简单情形有向图、无重边使用SPFAShortest Path Faster Algorithm求最短路——即 Bellman-Ford 的队列优化版本能正确处理负权边且常数小。该代码块在仓库中被标记为min_cost_flow_successive_shortest_path并由 test/extract_snippets.py 自动抽取为头文件参与自动化测试详见下文仓库测试体系一节。核心数据结构struct Edge { int from, to, capacity, cost; }; vectorvectorint adj, cost, capacity; const int INF 1e9;Edge输入边字段分别为起点、终点、容量、单位费用adj邻接表注意同时包含正向边与反向边的端点因为增广路会沿反向边回退cost/capacity按顶点对索引的费用矩阵与容量矩阵正反向共用同一对下标方向靠符号/增减区分INF足够大的无穷大需大于一切可能的路径费用和。最短路径求解SPFAvoid shortest_paths(int n, int v0, vectorint d, vectorint p) { d.assign(n, INF); d[v0] 0; vectorbool inq(n, false); queueint q; q.push(v0); p.assign(n, -1); while (!q.empty()) { int u q.front(); q.pop(); inq[u] false; for (int v : adj[u]) { if (capacity[u][v] 0 d[v] d[u] cost[u][v]) { d[v] d[u] cost[u][v]; p[v] u; if (!inq[v]) { inq[v] true; q.push(v); } } } } }要点解读松弛条件必须包含capacity[u][v] 0只有残量容量为正的边才能被用于寻路这是残量网络的定义直接体现沿反向边走时cost[u][v]为负因为反向边费用是正向边费用的相反数所以 SPFA 必须支持负权边——这也是这里不能直接用朴素 Dijkstra 的根本原因p[v]记录前驱顶点用于回溯增广路径。主流程min_cost_flowint min_cost_flow(int N, vectorEdge edges, int K, int s, int t) { adj.assign(N, vectorint()); cost.assign(N, vectorint(N, 0)); capacity.assign(N, vectorint(N, 0)); for (Edge e : edges) { adj[e.from].push_back(e.to); adj[e.to].push_back(e.from); cost[e.from][e.to] e.cost; cost[e.to][e.from] -e.cost; capacity[e.from][e.to] e.capacity; } int flow 0; int cost 0; vectorint d, p; while (flow K) { shortest_paths(N, s, d, p); if (d[t] INF) break; // find max flow on that path int f K - flow; int cur t; while (cur ! s) { f min(f, capacity[p[cur]][cur]); cur p[cur]; } // apply flow flow f; cost f * d[t]; cur t; while (cur ! s) { capacity[p[cur]][cur] - f; capacity[cur][p[cur]] f; cur p[cur]; } } if (flow K) return -1; else return cost; }流程与关键参数说明函数签名N为顶点数顶点编号 $0 \sim N-1$edges为输入边列表K为目标流量s、t为源点与汇点返回值为最小总费用若流量无法达到 $K$ 则返回-1建图阶段为每条边同时登记正向邻接与反向邻接正向费用为e.cost反向费用为-e.cost容量保持 0完全对应反向边 $C_{ji}-C_{ij}$的定义每轮迭代调用shortest_paths求残量网络最短路若d[t] INF说明 $s$、$t$ 已不连通跳出循环计算增广量先令f K - flow兜底防止超流量再沿路径取各边残量容量的最小值应用流量累计flow并以cost f * d[t]累加费用d[t]即该路径的总费用随后沿路径正边减f、反边加f完成残量网络更新收尾判断flow K说明不存在目标流量为 $K$ 的可行流返回-1否则返回累计的最小总费用。注意该实现采用顶点对矩阵存储因此直接限定在有向且无重边的图上使用处理多重图需按原文档无向图与多重图一节所述改造每条边独立存储、记录前驱边编号、显式维护反向边编号。仓库测试体系代码正确性的自动化验证该实现并非仅停留在文档层面仓库内置了完整的自动化测试闭环验证链路如下代码抽取test/extract_snippets.py 会遍历src/下所有.md文件用正则^\s*\{.cpp\sfile(\S)\}$匹配带file标记的代码块将其内容写入test/目录下同名.h头文件本实现对应min_cost_flow_successive_shortest_path.h编译与运行test/test.sh 逐个编译test/*.cpp-stdc17并开启-fsanitizeundefined运行后以退出码判定通过与否断言验证test/test_min_cost_flow.cpp 用#include min_cost_flow_successive_shortest_path.h直接复用该实现对两组网络逐K值断言返回费用第一组来自 TopCoder 的经典示例包含 8 个顶点、12 条边其中从源点 $0$ 到汇点 $7$ 的边费用为 0内部边费用各异edges {1→2(3,1), 1→3(3,4), 2→3(7,2), 3→6(1,8), 3→5(6,5), 3→4(5,2), 4→5(3,1), 0→1(5,0), 0→2(2,0), 4→7(2,0), 5→7(4,0), 6→7(1,0)} expected {0, 4, 8, 14, 20, 26, 35, 47, -1}对K 0..8依次断言流量 0 时费用为 0随流量逐级增大的最优费用序列为4, 8, 14, 20, 26, 35, 47当K 8时超出网络最大流量断言返回-1——这恰好验证了流量不足 $K$ 时返回 -1的收尾逻辑。第二组为 4 顶点、5 边的稠密小网络期望费用序列为0, 5, 10, 18, 29, 40, -1同样覆盖了从零流量到不可行流量的完整区间。这份测试既是实现正确性的证据也是读者本地验证与二次开发的参考基线。在仓库中的关联应用指派问题最小费用流是仓库内多个高级问题的底层引擎。最具代表性的是 src/graph/Assignment-problem-min-flow.md它将N×N 指派问题选 $N$ 个元素每行每列恰好一个使总和最小建模为二部流量网络——源点连左部行/订单、左右部之间以容量 1、费用 $A_{ij}$ 相连、右部连汇点然后求解最小费用最大流其最优性直接来自最小费用流本身的定义。该文还给出复杂度结论采用 Dijkstra 时为 $O(N^3)$采用 Bellman-Ford 时为 $O(N^4)$。此外 src/graph/hungarian-algorithm.md 也明确指出匈牙利算法可被视作逐次最短路算法在指派问题上的特化。这些文档共同构成了最大流 → 最小费用流 → 指派问题的递进知识链。实战要点小结两种问题统一求解固定流量 $K$ 与最大流变体共用同一算法只需调整 $K$ 的取值反向边是灵魂负费用反向边让算法具备撤销与重路由能力代价是寻路必须支持负权SPFA/Bellman-Ford或引入 Johnson 势能注意图的类型有向无重图可直接套用本实现无向图/多重图需要额外的边级存储与编号管理提前终止与不可行判定最后一轮增广量需以K - flow兜底当 $s$、$t$ 不连通而流量未达 $K$ 时返回-1表示目标流量不可行复杂度警示算法最坏情况为 $O(F \cdot T)$对流量很大的网络需谨慎评估必要时改用势能 Dijkstra 或与 Dinic 结合的优化变体。如需进一步阅读可在仓库内对照 src/graph/min_cost_flow.md、src/graph/edmonds_karp.md、src/graph/bellman_ford.md 与 src/graph/Assignment-problem-min-flow.md 组合研读并以 test/test_min_cost_flow.cpp 作为本地验证起点。赞分享文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载相关推荐TypeScript 类型导入完全指南用 import type 消除运行时副作用Front-End-Checklist 实践篇TypeScript 类型导入完全指南用 import type 消除运行时副作用Front End Checklist 实践篇 本指南以 skills/文档教程知识库全局最小割Global Minimum Cut的 Stoer-Wagner 算法详解——cp-algorithms 仓库实现与验证全局最小割Global Minimum Cut的 Stoer Wagner 算法详解——cp algorithms 仓库实现与验证 本文以 cp algor文档教程知识库JSLT函数声明与模块化打造可复用的JSON转换工具库JSLT函数声明与模块化打造可复用的JSON转换工具库 JSLTJSON query and transformation language是一款强大的J上一篇DBeaver数据库角色权限分析可视化权限继承与分配关系下一篇ArchiveBox命令行完全指南从入门到精通的15核心指令详解创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 cp-algorithms 最小费用流（Minimum-cost Flow）：逐次最短路算法完整解析
文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载导读本文聚焦于 cp-algorithms 仓库中 src/graph/min_cost_flow.md 所讲解的最小费用流问题及其经典解法——逐次最短路Successive Shortest Path算法。该算法是最大流算法Edmonds-Karp在带权边费用场景下的直接推广既能求解给定流量 $K$ 的最小费用流也能通过令 $K \to \infty$ 求解最小费用最大流。读完本文你将掌握最小费用流问题的数学模型、残量网络的构造、算法的正确性前提与复杂度上界以及仓库中基于 SPFA 的完整可运行 C 实现并了解该算法在仓库内其他文档如指派问题中的应用。问题定义最小费用流与最小费用最大流给定一个由 $n$ 个顶点、$m$ 条边构成的网络 $G$。每条边通常为有向边带两个整数属性容量capacity非负整数 $U_{ij}$表示该边上可承载的流量上限费用cost整数 $C_{ij}$表示沿该边运输每单位流量的代价。同时网络中标定了源点 $s$与汇点 $t$。对于给定的目标流量值 $K$需要找到流量恰好为 $K$的可行流并且在该类流量中使总费用最低。这一问题被称为最小费用流问题minimum-cost flow problem。另一种常见表述是先求出最大流再在所有最大流中选取总费用最小的那个即最小费用最大流问题minimum-cost maximum-flow problem。两种变体都可以用逐次最短路算法统一求解——原文档指出It is not difficult to see, that if we set $K$ to infinity, then the algorithm will find the minimum-cost maximum-flow.算法总览与 Edmonds-Karp 的血缘关系逐次最短路算法与仓库中 Edmonds-Karp 最大流算法 在结构上高度相似两者都反复在残量网络中寻找一条从 $s$ 到 $t$ 的增广路并沿路径推送尽可能多的流量。唯一的关键区别在于寻路的度量标准Edmonds-Karp 用 BFS 找边数最少的增广路逐次最短路算法找费用之和最小的增广路最短路径意义上的最短。这一改动使得每轮增广得到的都是当前流下的最优边际增广从而保证了最终结果的总费用最小。最短路部分的计算可直接复用仓库中的 Bellman-Ford含其 SPFA 变体或经过势能改造的 Dijkstra。最简单情形有向图且无重边先考察最简情形图是有向的且任意一对顶点之间至多有一条边若存在 $(i,j)$则不允许同时存在 $(j,i)$。符号约定$U_{ij}$边 $(i,j)$ 的容量$C_{ij}$边 $(i,j)$ 的单位流量费用$F_{ij}$边 $(i,j)$ 上当前的流量初始全部为 $0$。构造反向边对每条边 $(i,j)$ 加入反向边$(j,i)$其容量 $U_{ji}0$、费用 $C_{ji}-C_{ij}$。由于最简情形保证 $(j,i)$ 原本不存在于网络中加入反向边后网络仍然不是多重图。算法运行全程保持对称条件$$F_{ji} -F_{ij}$$也就是说沿着反向边撤销流量等价于把正向边的流量取负号。反向边是让算法能够回收已推送流量、重新路由的关键机制——这正是流算法区别于普通贪心路径搜索的核心。残量网络对固定流 $F$定义残量网络residual network其语义与 Ford-Fulkerson 方法 中完全一致残量网络只包含未饱和的边即满足 $F_{ij} U_{ij}$ 的边每条这样的边其残量容量为$$R_{ij} U_{ij} - F_{ij}$$注意反向边同样参与残量网络的构成当正向边已有流量 $F_{ij} 0$ 时反向边 $(j,i)$ 的残量容量 $R_{ji} U_{ji} - F_{ji} 0 - (-F_{ij}) F_{ij} 0$因此它是一条可用的回退边费用为 $-C_{ij}$。这正是算法能够对已推送的流量进行重新调度的原因。逐次最短路迭代流程初始化所有流量为 $0$构建含反向边的网络在残量网络中寻找从 $s$ 到 $t$ 的费用最短路径不是边数最短若不存在这样的路径当前流量尚未达到 $K$则说明流量为 $K$ 的可行流根本不存在算法终止否则 $F$ 即为所求。若找到路径则沿路径尽可能多地增广取路径上所有边残量容量 $R_{ij}$ 的最小值作为可增广量正向边流量增加该值反向边相应减少若流量在某轮达到 $K$立即停止。需要注意最后一轮只需增广到使总流量恰好为 $K$ 的量即可代码中体现为f min(f, K - flow)不要让最终流量超过 $K$。从算法流程可以直接看出把 $K$ 设为无穷大迭代会一直持续到残量网络中 $s$ 与 $t$ 不再连通此时得到的正是最小费用最大流。无向图与多重图实现的额外考量原文档明确指出无向图或多重图在概念上与上述算法并无差别算法同样可以工作但实现会更复杂。原因是无向边的拆分。一条无向边 $(i,j)$ 等价于两条容量、费用都相同的有向边 $(i,j)$ 与 $(j,i)$。由于逐次最短路算法会为每条有向边再生成一条反向边一条无向边最终会被拆成4 条有向边网络事实上变成了多重图。多重边带来的三个实现要求每条多重边的流量必须分开存储——不能用一对顶点对应一条边的简单矩阵或邻接数组寻路时必须区分具体是哪一条边被选入路径——除常规的前驱顶点数组p[]外还必须额外记录从哪条边走过来即前驱边编号否则无法正确回溯增广路径增广后必须沿对应反向边回退——由于存在多条平行边必须为每条边显式存储其反向边的编号。除以上三点外无向图与多重图不再有其他障碍。复杂度分析理论边界与势能加速该算法在最坏情况下是指数级的每轮增广可能只推送 1 单位流量因此要得到流量大小为 $F$ 的最小费用流最坏需要 $O(F)$ 轮迭代。若每次寻路花费 $T$则总复杂度为$$O(F \cdot T)$$其中 $T$ 是从源到汇求最短路径所需时间。原文档给出了两种具体配置寻路算法单轮寻路 $T$总复杂度Bellman-Ford / SPFA$O(nm)$$O(F \cdot mn)$经势能改造的 Dijkstra堆优化初始预处理 $O(nm)$之后每轮 $O(m \log n)$$O(mn F \cdot m \log n)$后者的核心是Johnson 势能potentials思想由于残量网络中存在费用为负的反向边不能直接套用 Dijkstra需要先做一轮 Bellman-Ford 求出每个顶点的势能把负权边转化为非负权再逐轮用 Dijkstra 加速。可参考仓库中的 Dijkstra 稠密图实现 与 稀疏图堆优化实现 理解底层寻路逻辑。原文档还提到可以进一步将势能思想与Dinic 算法结合把迭代轮数从 $F$ 压缩到 $\min(F, nC)$其中 $C$ 是网络中边费用的最大值。实现基于 SPFA 的逐次最短路附完整源码原文档给出的实现针对最简单情形有向图、无重边使用SPFAShortest Path Faster Algorithm求最短路——即 Bellman-Ford 的队列优化版本能正确处理负权边且常数小。该代码块在仓库中被标记为min_cost_flow_successive_shortest_path并由 test/extract_snippets.py 自动抽取为头文件参与自动化测试详见下文仓库测试体系一节。核心数据结构struct Edge { int from, to, capacity, cost; }; vectorvectorint adj, cost, capacity; const int INF 1e9;Edge输入边字段分别为起点、终点、容量、单位费用adj邻接表注意同时包含正向边与反向边的端点因为增广路会沿反向边回退cost/capacity按顶点对索引的费用矩阵与容量矩阵正反向共用同一对下标方向靠符号/增减区分INF足够大的无穷大需大于一切可能的路径费用和。最短路径求解SPFAvoid shortest_paths(int n, int v0, vectorint d, vectorint p) { d.assign(n, INF); d[v0] 0; vectorbool inq(n, false); queueint q; q.push(v0); p.assign(n, -1); while (!q.empty()) { int u q.front(); q.pop(); inq[u] false; for (int v : adj[u]) { if (capacity[u][v] 0 d[v] d[u] cost[u][v]) { d[v] d[u] cost[u][v]; p[v] u; if (!inq[v]) { inq[v] true; q.push(v); } } } } }要点解读松弛条件必须包含capacity[u][v] 0只有残量容量为正的边才能被用于寻路这是残量网络的定义直接体现沿反向边走时cost[u][v]为负因为反向边费用是正向边费用的相反数所以 SPFA 必须支持负权边——这也是这里不能直接用朴素 Dijkstra 的根本原因p[v]记录前驱顶点用于回溯增广路径。主流程min_cost_flowint min_cost_flow(int N, vectorEdge edges, int K, int s, int t) { adj.assign(N, vectorint()); cost.assign(N, vectorint(N, 0)); capacity.assign(N, vectorint(N, 0)); for (Edge e : edges) { adj[e.from].push_back(e.to); adj[e.to].push_back(e.from); cost[e.from][e.to] e.cost; cost[e.to][e.from] -e.cost; capacity[e.from][e.to] e.capacity; } int flow 0; int cost 0; vectorint d, p; while (flow K) { shortest_paths(N, s, d, p); if (d[t] INF) break; // find max flow on that path int f K - flow; int cur t; while (cur ! s) { f min(f, capacity[p[cur]][cur]); cur p[cur]; } // apply flow flow f; cost f * d[t]; cur t; while (cur ! s) { capacity[p[cur]][cur] - f; capacity[cur][p[cur]] f; cur p[cur]; } } if (flow K) return -1; else return cost; }流程与关键参数说明函数签名N为顶点数顶点编号 $0 \sim N-1$edges为输入边列表K为目标流量s、t为源点与汇点返回值为最小总费用若流量无法达到 $K$ 则返回-1建图阶段为每条边同时登记正向邻接与反向邻接正向费用为e.cost反向费用为-e.cost容量保持 0完全对应反向边 $C_{ji}-C_{ij}$的定义每轮迭代调用shortest_paths求残量网络最短路若d[t] INF说明 $s$、$t$ 已不连通跳出循环计算增广量先令f K - flow兜底防止超流量再沿路径取各边残量容量的最小值应用流量累计flow并以cost f * d[t]累加费用d[t]即该路径的总费用随后沿路径正边减f、反边加f完成残量网络更新收尾判断flow K说明不存在目标流量为 $K$ 的可行流返回-1否则返回累计的最小总费用。注意该实现采用顶点对矩阵存储因此直接限定在有向且无重边的图上使用处理多重图需按原文档无向图与多重图一节所述改造每条边独立存储、记录前驱边编号、显式维护反向边编号。仓库测试体系代码正确性的自动化验证该实现并非仅停留在文档层面仓库内置了完整的自动化测试闭环验证链路如下代码抽取test/extract_snippets.py 会遍历src/下所有.md文件用正则^\s*\{.cpp\sfile(\S)\}$匹配带file标记的代码块将其内容写入test/目录下同名.h头文件本实现对应min_cost_flow_successive_shortest_path.h编译与运行test/test.sh 逐个编译test/*.cpp-stdc17并开启-fsanitizeundefined运行后以退出码判定通过与否断言验证test/test_min_cost_flow.cpp 用#include min_cost_flow_successive_shortest_path.h直接复用该实现对两组网络逐K值断言返回费用第一组来自 TopCoder 的经典示例包含 8 个顶点、12 条边其中从源点 $0$ 到汇点 $7$ 的边费用为 0内部边费用各异edges {1→2(3,1), 1→3(3,4), 2→3(7,2), 3→6(1,8), 3→5(6,5), 3→4(5,2), 4→5(3,1), 0→1(5,0), 0→2(2,0), 4→7(2,0), 5→7(4,0), 6→7(1,0)} expected {0, 4, 8, 14, 20, 26, 35, 47, -1}对K 0..8依次断言流量 0 时费用为 0随流量逐级增大的最优费用序列为4, 8, 14, 20, 26, 35, 47当K 8时超出网络最大流量断言返回-1——这恰好验证了流量不足 $K$ 时返回 -1的收尾逻辑。第二组为 4 顶点、5 边的稠密小网络期望费用序列为0, 5, 10, 18, 29, 40, -1同样覆盖了从零流量到不可行流量的完整区间。这份测试既是实现正确性的证据也是读者本地验证与二次开发的参考基线。在仓库中的关联应用指派问题最小费用流是仓库内多个高级问题的底层引擎。最具代表性的是 src/graph/Assignment-problem-min-flow.md它将N×N 指派问题选 $N$ 个元素每行每列恰好一个使总和最小建模为二部流量网络——源点连左部行/订单、左右部之间以容量 1、费用 $A_{ij}$ 相连、右部连汇点然后求解最小费用最大流其最优性直接来自最小费用流本身的定义。该文还给出复杂度结论采用 Dijkstra 时为 $O(N^3)$采用 Bellman-Ford 时为 $O(N^4)$。此外 src/graph/hungarian-algorithm.md 也明确指出匈牙利算法可被视作逐次最短路算法在指派问题上的特化。这些文档共同构成了最大流 → 最小费用流 → 指派问题的递进知识链。实战要点小结两种问题统一求解固定流量 $K$ 与最大流变体共用同一算法只需调整 $K$ 的取值反向边是灵魂负费用反向边让算法具备撤销与重路由能力代价是寻路必须支持负权SPFA/Bellman-Ford或引入 Johnson 势能注意图的类型有向无重图可直接套用本实现无向图/多重图需要额外的边级存储与编号管理提前终止与不可行判定最后一轮增广量需以K - flow兜底当 $s$、$t$ 不连通而流量未达 $K$ 时返回-1表示目标流量不可行复杂度警示算法最坏情况为 $O(F \cdot T)$对流量很大的网络需谨慎评估必要时改用势能 Dijkstra 或与 Dinic 结合的优化变体。如需进一步阅读可在仓库内对照 src/graph/min_cost_flow.md、src/graph/edmonds_karp.md、src/graph/bellman_ford.md 与 src/graph/Assignment-problem-min-flow.md 组合研读并以 test/test_min_cost_flow.cpp 作为本地验证起点。赞分享文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载相关推荐TypeScript 类型导入完全指南用 import type 消除运行时副作用Front-End-Checklist 实践篇TypeScript 类型导入完全指南用 import type 消除运行时副作用Front End Checklist 实践篇 本指南以 skills/文档教程知识库全局最小割Global Minimum Cut的 Stoer-Wagner 算法详解——cp-algorithms 仓库实现与验证全局最小割Global Minimum Cut的 Stoer Wagner 算法详解——cp algorithms 仓库实现与验证 本文以 cp algor文档教程知识库JSLT函数声明与模块化打造可复用的JSON转换工具库JSLT函数声明与模块化打造可复用的JSON转换工具库 JSLTJSON query and transformation language是一款强大的J上一篇DBeaver数据库角色权限分析可视化权限继承与分配关系下一篇ArchiveBox命令行完全指南从入门到精通的15核心指令详解创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考