1. 项目概述从算法竞赛到工程实践的网络流费用流如果你在C/C领域摸爬滚打了一段时间无论是准备算法竞赛还是处理一些复杂的资源调度、路径规划类工程问题大概率会碰到“网络流”和“费用流”这两个词。它们听起来有点抽象像是数学建模里的概念但实际上它们是解决一大类“有限资源最优分配”问题的利器。简单来说网络流帮你算“最大能运多少货”而费用流则更进一步告诉你“在运力范围内怎么运最省钱”。我最早接触是在大学搞ACM的时候为了解一道“食堂窗口排队”的模拟题硬啃了Dinic和SPFA。后来在工作中做任务调度系统需要把一堆计算任务合理地分配到不同的服务器节点上既要保证总完成时间最短最小费用又要不超负荷最大流限制才发现当年学的那些模板和思想在这里派上了大用场。网络流费用流的代码从竞赛时追求极致速度的“奇技淫巧”到工程中更注重清晰和健壮性的实现这个转变过程本身就充满了值得分享的细节。这篇文章我就以一个过来人的身份和你聊聊在C/C里实现网络流和费用流那些事儿。我会从最基础的概念模型讲起然后手把手带你实现两个最经典、最实用的算法用于求最大流的Dinic算法和用于求最小费用最大流的SPFA或Primal-Dual 费用流算法。不止是给你可以“CtrlC/V”的代码模板更重要的是拆解每一步背后的“为什么”——为什么用邻接表而不用邻接矩阵为什么反向边的容量是0而费用是负的SPFA都“死”了为什么费用流里还能用这些才是你真正掌握并能灵活应用的关键。无论你是正在刷题的学生还是需要解决实际分配问题的开发者这篇文章都能给你一套从理论到实践、可直接复用的解决方案。我们会用C来写因为它的STL容器和模板在构建图结构时非常方便性能也足够应对大多数场景。2. 核心概念与问题建模把现实问题抽象成一张图在动手写代码之前我们必须先统一“语言”。网络流的所有算法都建立在几个核心概念和一张精心构建的图上。2.1 网络流图的基本要素你可以把网络流图想象成一个自来水系统。有一个水源点源点Source 常记为s一个汇水点汇点Sink 常记为t中间是错综复杂的管道边Edges。每个管道有它的粗细也就是容量Capacity表示单位时间内最多能流过多大的水量。最初所有管道都是空的水开始从源点流出经过管道网络最终汇入汇点。在任何时刻每条管道中实际流过的水量不能超过它的容量并且除了源点和汇点流入任何一个中间节点的水量必须等于流出的水量就像水流守恒。满足这些条件的一个水流方案就是一个可行流。而所有可行流中从源点净流出流量最大的那个就是最大流。当我们引入“运费”的概念时就得到了费用流。现在每条管道除了容量还有一个属性单位流量通过所需的费用Cost。我们的目标可能有两个一是在达到最大流的前提下使得总费用最小最小费用最大流二是在给定一个流量目标下找出输送这些流量的最小费用方案最小费用流。前者更常见。2.2 如何将实际问题建模为网络流这是最关键的一步决定了你能否正确解决问题。核心是识别出问题中的“流”、“节点”、“边的容量与费用”。经典案例1任务分配假设有m个任务和n台机器每个任务只能分配给特定的几台机器完成每台机器有处理上限。任务i分配给机器j需要花费c_ij。如何分配使总花费最小建模建立源点s连接每个任务节点容量为1每个任务只需分配一次费用0。每个任务节点连接到它能用的机器节点容量为1一个任务给一台机器费用为c_ij。每个机器节点连接到汇点t容量为该机器的处理上限费用0。求解从s到t的最小费用最大流流值即为能分配的最大任务数方案就在流的路径中。经典案例2运输问题多个仓库向多个市场运货每个仓库有库存每个市场有需求每条运输路线有运力上限和单位运费。如何安排运输在满足需求的同时成本最低建模源点s连接仓库节点容量为库存费用0。仓库节点连接市场节点容量为路线运力费用为运费。市场节点连接汇点t容量为需求费用0。这几乎是最标准的费用流模型。建模的心得流的含义流通常代表被分配、传输的“物品”或“资源”的数量如任务、货物、数据包。节点的含义节点可以是物理位置仓库、市场、决策状态任务、机器、或者时间分层用于处理时间相关的约束。边的容量限制的是“流”的通过上限。它可以表示资源限制、处理能力、时间窗口等。边的费用表示进行该分配或传输所产生的成本。注意建模时经常需要用到“拆点”的技巧。如果一个节点有容量限制例如一个中转站每小时只能处理10辆车就需要把这个节点拆成一个“入点”和一个“出点”然后在它们之间连一条边边的容量就是这个节点的处理上限。这是处理“点容量”问题的标准手法。2.3 算法选择的总体思路明确了模型接下来选算法。对于最大流最流行、综合性能最好的就是Dinic算法它结合了BFS分层和DFS多路增广在大多数稀疏图上效率很高。对于最小费用最大流最经典、实现相对简单的是基于SPFAShortest Path Faster Algorithm的费用流算法也常被称为MCMF。虽然SPFA在最坏情况下时间复杂度不理想但在费用流常见的、边权费用可能为负的残余网络中它比Dijkstra更直接且在实际的问题数据中往往表现不错。更高级的会有基于Primal-Dual原始对偶和势函数的Dijkstra优化版本但SPFA版本是理解和入门的绝佳起点。我们的实现路线就定为先实现一个高效、健壮的最大流Dinic算法然后在其基础上增加费用的维度实现SPFA费用流算法。3. 基础构建图的数据结构与最大流Dinic实现工欲善其事必先利其器。一个良好的图数据结构是高效实现网络流算法的基石。3.1 邻接表与“成对存储”技巧我们选择使用邻接表来存图而不是邻接矩阵。原因很简单网络流图通常是稀疏的边数远小于节点数的平方邻接表在空间和时间上都更优。C中我们用vector来动态存储每个节点的出边列表。这里有一个实现网络流必须掌握的“魔术技巧”成对存储又称“奇偶边”技巧。为了在寻找增广路后能方便地更新反向边用于“反悔”我们在加一条从u到v容量为cap的边时会同时加入它的反向边v-u初始容量为0。为了能通过一条边快速找到它的反向边我们让正向边和反向边在存储数组中成对出现。通常约定下标为0, 2, 4...的是正向边下标为1, 3, 5...的是对应的反向边。这样对于任意一条边e它的反向边就是e ^ 1异或1操作。这个技巧省去了额外的查找开销是竞赛和高效实现中的标配。#include bits/stdc.h using namespace std; struct Edge { int to; // 边的终点 int rev; // 反向边在邻接表中的下标在旧式实现中常用 long long cap; // 边的剩余容量 // 注意在纯最大流中暂时没有cost字段 }; class Dinic { private: int n; // 节点数包括源点和汇点 vectorint level, iter; // BFS的层级DFS的当前弧优化迭代器 vectorvectorEdge graph; // 邻接表 // BFS构建分层图判断是否存在从s到t的增广路 bool bfs(int s, int t) { level.assign(n, -1); queueint q; level[s] 0; q.push(s); while (!q.empty()) { int u q.front(); q.pop(); for (const auto e : graph[u]) { if (e.cap 0 level[e.to] 0) { // 有剩余容量且未访问 level[e.to] level[u] 1; if (e.to t) return true; // 提前终止优化 q.push(e.to); } } } return level[t] 0; // 能否到达汇点 } // DFS在当前分层图上寻找增广路并增广 long long dfs(int u, int t, long long f) { if (u t) return f; for (int i iter[u]; i (int)graph[u].size(); i) { // 当前弧优化 Edge e graph[u][i]; if (e.cap 0 level[u] level[e.to]) { long long d dfs(e.to, t, min(f, e.cap)); if (d 0) { e.cap - d; // 更新正向边容量 graph[e.to][e.rev].cap d; // 更新反向边容量 return d; } } } return 0; // 无法增广 } public: Dinic(int node_count) : n(node_count), graph(node_count) {} // 添加一条从u到v容量为cap的有向边 void add_edge(int u, int v, long long cap) { // 正向边 graph[u].push_back((Edge){v, (int)graph[v].size(), cap}); // 反向边 graph[v].push_back((Edge){u, (int)graph[u].size() - 1, 0}); // 注意反向边初始容量为0 } // 计算从s到t的最大流 long long max_flow(int s, int t) { long long flow 0; const long long INF 1e18; while (bfs(s, t)) { iter.assign(n, 0); // 重置当前弧 long long f; while ((f dfs(s, t, INF)) 0) { flow f; } } return flow; } };3.2 Dinic算法核心步骤详解上面的代码实现了完整的Dinic算法。我们来拆解几个关键点BFS构建分层图 (bfs函数)这一步的目的是按照距离源点的最短距离边数给所有节点“分层”。level[u]表示节点u所在的层数源点为0。在DFS增广时我们只允许从低层节点走向高层节点level[u] level[e.to]。这保证了我们找到的增广路是最短路径之一避免了DFS在环里绕圈子是Dinic高效的核心。DFS多路增广 (dfs函数)在分层图的基础上进行DFS寻找一条从源点到汇点的路径并尽可能多地推送流量min(f, e.cap)。一旦找到一条路径就立即更新路径上所有边的容量正向边减反向边加并返回推送的流量。当前弧优化 (iter数组)这是Dinic算法的另一个重要优化。对于每个节点在一次BFS后的多轮DFS中如果某条边已经被“榨干”容量为0或者确定从它出发无法到达汇点那么在后续的DFS中就不需要再检查这条边了。iter[u]记录的就是节点u的下一次应该从哪条边开始尝试。for (int i iter[u]; ...)这个引用写法非常巧妙在递归返回时i的值会被保留实现了“跳过已处理边”的效果。反向边的更新注意dfs函数中的两行e.cap - d; graph[e.to][e.rev].cap d;这实现了“反悔”机制。推送了d的流量后正向边的容量减少d意味着这条边还能容纳cap-d的流量。同时反向边的容量增加d。你可以理解为反向边容量的增加为后续的增广提供了“退回”这d单位流量的可能性从而让算法能找到全局最优的流分布。实操心得与避坑指南容量类型务必使用long long。最大流的值可能很大用int在复杂图上很容易溢出导致结果错误或死循环。图的初始化n必须是节点的总数量通常从0或1开始连续编号。在调用add_edge前确保u和v在[0, n-1]范围内。反向边的revadd_edge中正向边的rev存的是反向边在graph[v]中的下标而反向边的rev存的是正向边在graph[u]中的下标。这个设计确保了graph[e.to][e.rev]总能精准地找到反向边对象。这是比“异或1”更直观的一种实现尤其在需要存储额外信息如费用时更清晰。INF 的设置dfs的初始流量f用一个很大的数如1e18。因为long long最大约9e18所以1e18是安全的。不要用INT_MAX。4. 进阶实现最小费用最大流SPFA 增广在最大流的基础上引入费用目标就变成了在保证流最大的前提下总费用最小。算法的核心思想没变不断寻找从源点到汇点的“最短增广路”并增广。只不过这里的“短”指的是路径上单位费用之和最小。4.1 SPFA寻找最小费用增广路为什么用SPFA因为在增广过程中我们会不断添加反向边。反向边的费用是正向边费用的相反数这是为了正确计算“反悔”操作带来的费用变化。这会导致图中存在负权边而Dijkstra算法不能直接处理负权图。SPFA可以处理负权虽然最坏复杂度高但在费用流这种特殊图每次增广只改变少量边上通常表现良好。我们需要修改边的结构体加入cost单位费用字段。同时在寻找增广路时我们不仅要记录到达每个点的最小费用dist还要记录路径的前驱边prevv和preve以便增广后能更新边的容量。struct MinCostEdge { int to; int rev; // 反向边在邻接表中的索引 long long cap; long long cost; // 单位流量的费用 }; class MinCostMaxFlow { private: int n; vectorvectorMinCostEdge graph; vectorlong long dist; vectorint prevv, preve; // 前驱节点和前驱边 const long long INF 1e18; public: MinCostMaxFlow(int node_count) : n(node_count), graph(node_count) {} void add_edge(int from, int to, long long cap, long long cost) { // 正向边 graph[from].push_back((MinCostEdge){to, (int)graph[to].size(), cap, cost}); // 反向边初始容量为0费用为-cost graph[to].push_back((MinCostEdge){from, (int)graph[from].size() - 1, 0, -cost}); } // 最小费用流返回 (最小费用, 最大流) pairlong long, long long min_cost_flow(int s, int t, long long maxf INF) { long long flow 0, cost 0; // 使用SPFA寻找最小费用路径 while (flow maxf) { dist.assign(n, INF); dist[s] 0; bool inqueue[n]; memset(inqueue, 0, sizeof(inqueue)); queueint q; q.push(s); inqueue[s] true; // SPFA 过程 while (!q.empty()) { int u q.front(); q.pop(); inqueue[u] false; for (int i 0; i (int)graph[u].size(); i) { MinCostEdge e graph[u][i]; if (e.cap 0 dist[e.to] dist[u] e.cost) { dist[e.to] dist[u] e.cost; prevv[e.to] u; preve[e.to] i; if (!inqueue[e.to]) { q.push(e.to); inqueue[e.to] true; } } } } if (dist[t] INF) { break; // 无法再找到增广路 } // 沿着找到的路径增广尽可能多的流 long long d maxf - flow; for (int v t; v ! s; v prevv[v]) { d min(d, graph[prevv[v]][preve[v]].cap); } flow d; cost d * dist[t]; // 本次增广的费用 流量 * 路径总单位费用 // 更新残余网络 for (int v t; v ! s; v prevv[v]) { MinCostEdge e graph[prevv[v]][preve[v]]; e.cap - d; graph[v][e.rev].cap d; } } return {cost, flow}; } };4.2 算法流程与费用计算逻辑SPFA找最短路以边的单位费用作为路径权重寻找从源点s到汇点t的、且剩余容量大于0的路径中总费用最小的那条。dist[t]就是这条路径的单位流量总费用。确定增广流量沿着找到的路径从汇点t回溯到源点s找出路径上所有边剩余容量的最小值d。这就是本次能增广的流量。更新流量和费用总流量flow增加d。总费用cost增加d * dist[t]。这是算法的核心保证了每次增加的都是“当前状态下”单位费用最小的流量。更新残余网络和Dinic一样对路径上的每条边减少其容量d并增加其反向边的容量d。关键点在于反向边的费用是负的。为什么假设我们有一条边u-v容量5费用3。我们推送了1单位流量。正向边容量变为4。我们创建或增加了一条反向边v-u容量为1费用为-3。这意味着如果后续的增广路使用了这条反向边v-u就相当于“退回了”之前从u-v流过的1单位流量。这1单位流量当初产生了3的费用现在“退回”它自然应该在总费用中扣除3所以反向边的费用是-3。这个设计完美地保证了费用计算的正确性。实操中的关键细节SPFA的判负环在纯最短路问题中SPFA需要判断负环。但在费用流中由于每次增广后图的结构改变反向边产生通常不会出现无限循环的负环。所以我们的实现省略了负环判断更简洁。但在极端构造的数据下理论上可能存在性能问题这时就需要更高级的势函数Dijkstra方法。prevv和preve数组它们的大小必须是节点数n。prevv[v]记录到达节点v的路径上的前驱节点preve[v]记录的是从前驱节点prevv[v]的邻接表中具体是哪条边通向v的索引。这个设计是为了能快速定位到边对象并进行更新。费用溢出和容量一样总费用也可能很大务必使用long long。最大流限制min_cost_flow函数中的maxf参数允许你指定一个期望的最大流。如果只要求最小费用而不要求一定是最大流可以传入一个较小的值。默认INF表示一直增广直到无法继续。5. 性能优化与高级技巧从SPFA到Primal-Dual基础的SPFA费用流已经能解决很多问题但当图很大或者边权变化复杂时SPFA可能成为瓶颈。工业级的实现和高端竞赛中更常用的是Primal-Dual原始对偶算法它使用势函数Potential将所有边权变为非负从而允许使用更快的Dijkstra算法来寻找最短增广路。5.1 势函数Potential的原理势函数h[v]为每个节点赋予一个势能。对于一条边u-v定义其缩减费用Reduced Cost为e.cost h[u] - h[v]。神奇的是如果我们能维护一组势函数使得对于残余网络中的所有边其缩减费用都非负那么我们就可以在这个“改造后”的图上运行Dijkstra算法来求最短最小费用路径。初始时可以设置h[v] 0或者用一次SPFA求出初始最短路作为初始势。每次用Dijkstra求出基于缩减费用的最短路径dist后我们不仅用这条路径增广还要更新势函数h[v] dist[v]。这个更新规则能保证缩减费用始终保持非负。5.2 Primal-Dual 算法实现框架下面是基于势函数和Dijkstra的MinCostMaxFlow实现概要。它比纯SPFA版本更复杂但最坏情况下的时间复杂度更有保障。class MinCostMaxFlowPD { private: struct Edge { int to, rev; long long cap, cost; }; int n; vectorvectorEdge graph; vectorlong long potential, dist; vectorint prevv, preve; const long long INF 1e18; // 使用Dijkstra寻找最小费用路径基于缩减费用 bool dijkstra(int s, int t) { dist.assign(n, INF); using P pairlong long, int; priority_queueP, vectorP, greaterP pq; dist[s] 0; pq.emplace(0, s); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (dist[u] d) continue; // 旧的、无效的距离值 for (int i 0; i (int)graph[u].size(); i) { Edge e graph[u][i]; if (e.cap 0) continue; // 关键使用缩减费用 long long nd dist[u] e.cost potential[u] - potential[e.to]; if (dist[e.to] nd) { dist[e.to] nd; prevv[e.to] u; preve[e.to] i; pq.emplace(nd, e.to); } } } return dist[t] ! INF; } public: MinCostMaxFlowPD(int node_count) : n(node_count), graph(node_count), potential(node_count, 0) {} void add_edge(int from, int to, long long cap, long long cost) { graph[from].push_back({to, (int)graph[to].size(), cap, cost}); graph[to].push_back({from, (int)graph[from].size() - 1, 0, -cost}); } pairlong long, long long min_cost_flow(int s, int t, long long maxf INF) { long long flow 0, cost 0; // 可选用一次SPFA初始化势函数以处理初始负权边。 // 如果保证初始图无边权为负可以跳过。 // initialize_potential(s); while (flow maxf dijkstra(s, t)) { // 更新势函数 for (int i 0; i n; i) { if (dist[i] INF) potential[i] dist[i]; // 对于不可达点势函数保持不变或可设为INF } long long d maxf - flow; for (int v t; v ! s; v prevv[v]) { d min(d, graph[prevv[v]][preve[v]].cap); } flow d; cost d * (potential[t] - potential[s]); // 注意这里实际费用计算 for (int v t; v ! s; v prevv[v]) { Edge e graph[prevv[v]][preve[v]]; e.cap - d; graph[v][e.rev].cap d; } } return {cost, flow}; } };关键点解析费用计算在更新势函数后从s到t的实际路径费用等于(potential[t] - potential[s])而不是dist[t]。因为dist中存储的是缩减费用。这是一个常见的易错点。初始化势函数如果初始图中就存在负权边直接运行Dijkstra会出错。此时需要用一次SPFA或Bellman-Ford计算出初始的最短距离并将其作为初始势potential。代码中的initialize_potential(s)函数就是做这个的。如果题目保证初始边权非负可以省略。性能对比对于稠密图或精心构造的使SPFA变慢的数据Primal-Dual算法优势明显。但对于随机数据或稀疏图两者差距可能不大。SPFA版本代码更短更易于理解和调试通常是首选的实现方式。5.3 其他实用优化技巧多路增广Dinic思想融入费用流类似于Dinic我们也可以在费用流中先做一次BFS或Dijkstra进行分层然后在分层图上进行DFS多路增广。这可以减少最短路算法的调用次数在某些图上特别是容量较小而费用简单的图有奇效。这种算法有时被称为zkw费用流一种基于Dinic分层和DFS的费用流算法。但实现更复杂且并非在所有情况下都优于SPFA/Primal-Dual。容量缩放对于容量非常大的边可以借鉴最大流算法中的容量缩放思想从高位到低位逐步确定流量。在费用流中应用相对较少但在特定场景下有用。图的存储优化如果节点数非常多1e5使用vectorvectorEdge可能会有一定的缓存不友好问题。可以考虑用单一的边数组vectorEdge edges和每个节点的出边索引列表vectorint head[N]的“前向星”存图方式这在纯最大流中很常见但在需要频繁通过e.rev找反向边的费用流中实现起来稍显繁琐。6. 实战应用与调试案例分析与常见问题理论说得再多不如实际跑一跑。我们用一个经典问题来串联整个实现并分享调试中常见的“坑”。6.1 实战案例运输问题建模与求解假设有两个仓库A、B三个市场1、2、3。仓库A有货物50吨B有70吨。市场1、2、3分别需要30、40、60吨。运输路线及单位运费元/吨如下A-1: 10元运力无限A-2: 8元 运力无限A-3: 12元运力无限B-1: 9元 运力无限B-2: 11元运力无限B-3: 7元 运力无限求满足所有市场需求的最小总运费。建模节点源点s(0)仓库A(1)仓库B(2)市场1(3)市场2(4)市场3(5)汇点t(6)。共n7个节点。边s-A: 容量50费用0s-B: 容量70费用0A-市场1,2,3: 容量INF费用分别为10, 8, 12B-市场1,2,3: 容量INF费用分别为9, 11, 7市场1,2,3-t: 容量分别为30, 40, 60费用0求解我们调用MinCostMaxFlow的min_cost_flow函数目标流量应为304060130总需求。如果最大流小于130说明供不应求无解。否则返回的费用就是最小总运费。int main() { // 节点数s, A, B, m1, m2, m3, t 共7个 MinCostMaxFlow mcmf(7); int s 0, A 1, B 2, m1 3, m2 4, m3 5, t 6; const long long INF 1e18; // 源点到仓库 mcmf.add_edge(s, A, 50, 0); mcmf.add_edge(s, B, 70, 0); // 仓库到市场 mcmf.add_edge(A, m1, INF, 10); mcmf.add_edge(A, m2, INF, 8); mcmf.add_edge(A, m3, INF, 12); mcmf.add_edge(B, m1, INF, 9); mcmf.add_edge(B, m2, INF, 11); mcmf.add_edge(B, m3, INF, 7); // 市场到汇点 mcmf.add_edge(m1, t, 30, 0); mcmf.add_edge(m2, t, 40, 0); mcmf.add_edge(m3, t, 60, 0); auto [cost, flow] mcmf.min_cost_flow(s, t); if (flow 130) { cout 无法满足所有需求最大流为 flow endl; } else { cout 最小总运费为 cost 元 endl; cout 总运输量为 flow 吨 endl; } return 0; }运行后算法会计算出最优的运输方案。你可以通过检查最终每条边的容量减少值即流量来得知具体的运输量。6.2 常见问题、调试技巧与排查清单即使有了模板在实际编码中还是会遇到各种问题。下面是我踩过的一些坑和解决方法。问题1程序运行结果错误费用或流量不对。检查容量和费用类型确保都是long long。int溢出是新手最常见错误。检查反向边费用务必是-cost。这是费用流正确性的核心。检查图的构建节点编号是否从0开始连续add_edge的参数顺序(from, to, cap, cost)是否正确特别是源点和汇点不要弄错。验证模型用一个小到可以手算的案例测试。比如两个节点一条边看看最大流和费用是否正确。问题2程序陷入死循环或超时。检查SPFA/循环条件在SPFA中确保inqueue标记被正确维护。在min_cost_flow循环中确保有跳出条件dist[t] INF。检查负环虽然费用流中不常见但如果数据构造特殊SPFA可能因负环而不终止。可以添加计数器如果某个节点入队次数超过n节点数次则可能存在负环应终止算法。对于Primal-Dual算法则要检查初始势函数的设置。INF值过大在dfs或确定增广流量d时如果INF设置得太大接近LLONG_MAX在运算min(f, e.cap)时如果e.cap也是一个很大的数可能导致加法溢出变成负数。将INF设置为一个安全的大数如1e18。当前弧优化重置在Dinic中每次BFS后必须重置iter数组。忘记重置会导致算法提前终止得不到最大流。问题3如何输出具体的流方案算法结束后图中每条正向边(u-v)的初始容量original_cap减去剩余容量e.cap就是这条边上流过的流量。你可以在add_edge时将边的初始容量也存储下来例如在Edge结构体中加一个original_cap字段或者在添加边后用一个单独的数据结构记录初始图。求解完毕后遍历所有边计算flow_on_edge original_cap - current_cap。对于流量大于0的边输出u, v, flow_on_edge。问题4面对复杂问题建模没有思路怎么办识别“流”什么是在网络中流动的东西任务、货物、人员、数据识别“源”和“汇”流的起点和终点是什么识别“节点”和“边”节点代表状态、位置或决策点。边代表转移、运输或分配的可能性其容量限制流量费用代表成本。善用“拆点”这是解决节点容量、时间分层、状态转移问题的万能钥匙。如果一个节点有通过限制就拆成“入点”和“出点”中间连一条容量为限制的边。从简单开始先尝试构建一个最简模型再逐步添加约束。很多复杂问题都是经典模型如二分图匹配、任务分配、运输问题的变种。调试清单[ ] 所有int是否已改为long long容量、费用、距离、流量[ ] 反向边的容量是否为0费用是否为-cost[ ] 节点编号是否在[0, n-1]范围内n的值是否正确[ ] SPFA/Dijkstra中是否只考虑了cap 0的边[ ] 在更新残余网络时是否同时更新了正向边和反向边[ ]INF的值是否设置得合理足够大且不会在运算中溢出[ ] 如果需要输出方案是否记录了初始容量网络流和费用流的代码就像一把精密的瑞士军刀每个细节都关乎正确性。第一次实现时建议严格按照模板来写并通过大量练习来熟悉建模和调试。一旦掌握你会发现它能优雅地解决许多看似棘手的优化问题。从竞赛到工程这套思想的价值远超代码本身。
1. 项目概述从算法竞赛到工程实践的网络流费用流如果你在C/C领域摸爬滚打了一段时间无论是准备算法竞赛还是处理一些复杂的资源调度、路径规划类工程问题大概率会碰到“网络流”和“费用流”这两个词。它们听起来有点抽象像是数学建模里的概念但实际上它们是解决一大类“有限资源最优分配”问题的利器。简单来说网络流帮你算“最大能运多少货”而费用流则更进一步告诉你“在运力范围内怎么运最省钱”。我最早接触是在大学搞ACM的时候为了解一道“食堂窗口排队”的模拟题硬啃了Dinic和SPFA。后来在工作中做任务调度系统需要把一堆计算任务合理地分配到不同的服务器节点上既要保证总完成时间最短最小费用又要不超负荷最大流限制才发现当年学的那些模板和思想在这里派上了大用场。网络流费用流的代码从竞赛时追求极致速度的“奇技淫巧”到工程中更注重清晰和健壮性的实现这个转变过程本身就充满了值得分享的细节。这篇文章我就以一个过来人的身份和你聊聊在C/C里实现网络流和费用流那些事儿。我会从最基础的概念模型讲起然后手把手带你实现两个最经典、最实用的算法用于求最大流的Dinic算法和用于求最小费用最大流的SPFA或Primal-Dual 费用流算法。不止是给你可以“CtrlC/V”的代码模板更重要的是拆解每一步背后的“为什么”——为什么用邻接表而不用邻接矩阵为什么反向边的容量是0而费用是负的SPFA都“死”了为什么费用流里还能用这些才是你真正掌握并能灵活应用的关键。无论你是正在刷题的学生还是需要解决实际分配问题的开发者这篇文章都能给你一套从理论到实践、可直接复用的解决方案。我们会用C来写因为它的STL容器和模板在构建图结构时非常方便性能也足够应对大多数场景。2. 核心概念与问题建模把现实问题抽象成一张图在动手写代码之前我们必须先统一“语言”。网络流的所有算法都建立在几个核心概念和一张精心构建的图上。2.1 网络流图的基本要素你可以把网络流图想象成一个自来水系统。有一个水源点源点Source 常记为s一个汇水点汇点Sink 常记为t中间是错综复杂的管道边Edges。每个管道有它的粗细也就是容量Capacity表示单位时间内最多能流过多大的水量。最初所有管道都是空的水开始从源点流出经过管道网络最终汇入汇点。在任何时刻每条管道中实际流过的水量不能超过它的容量并且除了源点和汇点流入任何一个中间节点的水量必须等于流出的水量就像水流守恒。满足这些条件的一个水流方案就是一个可行流。而所有可行流中从源点净流出流量最大的那个就是最大流。当我们引入“运费”的概念时就得到了费用流。现在每条管道除了容量还有一个属性单位流量通过所需的费用Cost。我们的目标可能有两个一是在达到最大流的前提下使得总费用最小最小费用最大流二是在给定一个流量目标下找出输送这些流量的最小费用方案最小费用流。前者更常见。2.2 如何将实际问题建模为网络流这是最关键的一步决定了你能否正确解决问题。核心是识别出问题中的“流”、“节点”、“边的容量与费用”。经典案例1任务分配假设有m个任务和n台机器每个任务只能分配给特定的几台机器完成每台机器有处理上限。任务i分配给机器j需要花费c_ij。如何分配使总花费最小建模建立源点s连接每个任务节点容量为1每个任务只需分配一次费用0。每个任务节点连接到它能用的机器节点容量为1一个任务给一台机器费用为c_ij。每个机器节点连接到汇点t容量为该机器的处理上限费用0。求解从s到t的最小费用最大流流值即为能分配的最大任务数方案就在流的路径中。经典案例2运输问题多个仓库向多个市场运货每个仓库有库存每个市场有需求每条运输路线有运力上限和单位运费。如何安排运输在满足需求的同时成本最低建模源点s连接仓库节点容量为库存费用0。仓库节点连接市场节点容量为路线运力费用为运费。市场节点连接汇点t容量为需求费用0。这几乎是最标准的费用流模型。建模的心得流的含义流通常代表被分配、传输的“物品”或“资源”的数量如任务、货物、数据包。节点的含义节点可以是物理位置仓库、市场、决策状态任务、机器、或者时间分层用于处理时间相关的约束。边的容量限制的是“流”的通过上限。它可以表示资源限制、处理能力、时间窗口等。边的费用表示进行该分配或传输所产生的成本。注意建模时经常需要用到“拆点”的技巧。如果一个节点有容量限制例如一个中转站每小时只能处理10辆车就需要把这个节点拆成一个“入点”和一个“出点”然后在它们之间连一条边边的容量就是这个节点的处理上限。这是处理“点容量”问题的标准手法。2.3 算法选择的总体思路明确了模型接下来选算法。对于最大流最流行、综合性能最好的就是Dinic算法它结合了BFS分层和DFS多路增广在大多数稀疏图上效率很高。对于最小费用最大流最经典、实现相对简单的是基于SPFAShortest Path Faster Algorithm的费用流算法也常被称为MCMF。虽然SPFA在最坏情况下时间复杂度不理想但在费用流常见的、边权费用可能为负的残余网络中它比Dijkstra更直接且在实际的问题数据中往往表现不错。更高级的会有基于Primal-Dual原始对偶和势函数的Dijkstra优化版本但SPFA版本是理解和入门的绝佳起点。我们的实现路线就定为先实现一个高效、健壮的最大流Dinic算法然后在其基础上增加费用的维度实现SPFA费用流算法。3. 基础构建图的数据结构与最大流Dinic实现工欲善其事必先利其器。一个良好的图数据结构是高效实现网络流算法的基石。3.1 邻接表与“成对存储”技巧我们选择使用邻接表来存图而不是邻接矩阵。原因很简单网络流图通常是稀疏的边数远小于节点数的平方邻接表在空间和时间上都更优。C中我们用vector来动态存储每个节点的出边列表。这里有一个实现网络流必须掌握的“魔术技巧”成对存储又称“奇偶边”技巧。为了在寻找增广路后能方便地更新反向边用于“反悔”我们在加一条从u到v容量为cap的边时会同时加入它的反向边v-u初始容量为0。为了能通过一条边快速找到它的反向边我们让正向边和反向边在存储数组中成对出现。通常约定下标为0, 2, 4...的是正向边下标为1, 3, 5...的是对应的反向边。这样对于任意一条边e它的反向边就是e ^ 1异或1操作。这个技巧省去了额外的查找开销是竞赛和高效实现中的标配。#include bits/stdc.h using namespace std; struct Edge { int to; // 边的终点 int rev; // 反向边在邻接表中的下标在旧式实现中常用 long long cap; // 边的剩余容量 // 注意在纯最大流中暂时没有cost字段 }; class Dinic { private: int n; // 节点数包括源点和汇点 vectorint level, iter; // BFS的层级DFS的当前弧优化迭代器 vectorvectorEdge graph; // 邻接表 // BFS构建分层图判断是否存在从s到t的增广路 bool bfs(int s, int t) { level.assign(n, -1); queueint q; level[s] 0; q.push(s); while (!q.empty()) { int u q.front(); q.pop(); for (const auto e : graph[u]) { if (e.cap 0 level[e.to] 0) { // 有剩余容量且未访问 level[e.to] level[u] 1; if (e.to t) return true; // 提前终止优化 q.push(e.to); } } } return level[t] 0; // 能否到达汇点 } // DFS在当前分层图上寻找增广路并增广 long long dfs(int u, int t, long long f) { if (u t) return f; for (int i iter[u]; i (int)graph[u].size(); i) { // 当前弧优化 Edge e graph[u][i]; if (e.cap 0 level[u] level[e.to]) { long long d dfs(e.to, t, min(f, e.cap)); if (d 0) { e.cap - d; // 更新正向边容量 graph[e.to][e.rev].cap d; // 更新反向边容量 return d; } } } return 0; // 无法增广 } public: Dinic(int node_count) : n(node_count), graph(node_count) {} // 添加一条从u到v容量为cap的有向边 void add_edge(int u, int v, long long cap) { // 正向边 graph[u].push_back((Edge){v, (int)graph[v].size(), cap}); // 反向边 graph[v].push_back((Edge){u, (int)graph[u].size() - 1, 0}); // 注意反向边初始容量为0 } // 计算从s到t的最大流 long long max_flow(int s, int t) { long long flow 0; const long long INF 1e18; while (bfs(s, t)) { iter.assign(n, 0); // 重置当前弧 long long f; while ((f dfs(s, t, INF)) 0) { flow f; } } return flow; } };3.2 Dinic算法核心步骤详解上面的代码实现了完整的Dinic算法。我们来拆解几个关键点BFS构建分层图 (bfs函数)这一步的目的是按照距离源点的最短距离边数给所有节点“分层”。level[u]表示节点u所在的层数源点为0。在DFS增广时我们只允许从低层节点走向高层节点level[u] level[e.to]。这保证了我们找到的增广路是最短路径之一避免了DFS在环里绕圈子是Dinic高效的核心。DFS多路增广 (dfs函数)在分层图的基础上进行DFS寻找一条从源点到汇点的路径并尽可能多地推送流量min(f, e.cap)。一旦找到一条路径就立即更新路径上所有边的容量正向边减反向边加并返回推送的流量。当前弧优化 (iter数组)这是Dinic算法的另一个重要优化。对于每个节点在一次BFS后的多轮DFS中如果某条边已经被“榨干”容量为0或者确定从它出发无法到达汇点那么在后续的DFS中就不需要再检查这条边了。iter[u]记录的就是节点u的下一次应该从哪条边开始尝试。for (int i iter[u]; ...)这个引用写法非常巧妙在递归返回时i的值会被保留实现了“跳过已处理边”的效果。反向边的更新注意dfs函数中的两行e.cap - d; graph[e.to][e.rev].cap d;这实现了“反悔”机制。推送了d的流量后正向边的容量减少d意味着这条边还能容纳cap-d的流量。同时反向边的容量增加d。你可以理解为反向边容量的增加为后续的增广提供了“退回”这d单位流量的可能性从而让算法能找到全局最优的流分布。实操心得与避坑指南容量类型务必使用long long。最大流的值可能很大用int在复杂图上很容易溢出导致结果错误或死循环。图的初始化n必须是节点的总数量通常从0或1开始连续编号。在调用add_edge前确保u和v在[0, n-1]范围内。反向边的revadd_edge中正向边的rev存的是反向边在graph[v]中的下标而反向边的rev存的是正向边在graph[u]中的下标。这个设计确保了graph[e.to][e.rev]总能精准地找到反向边对象。这是比“异或1”更直观的一种实现尤其在需要存储额外信息如费用时更清晰。INF 的设置dfs的初始流量f用一个很大的数如1e18。因为long long最大约9e18所以1e18是安全的。不要用INT_MAX。4. 进阶实现最小费用最大流SPFA 增广在最大流的基础上引入费用目标就变成了在保证流最大的前提下总费用最小。算法的核心思想没变不断寻找从源点到汇点的“最短增广路”并增广。只不过这里的“短”指的是路径上单位费用之和最小。4.1 SPFA寻找最小费用增广路为什么用SPFA因为在增广过程中我们会不断添加反向边。反向边的费用是正向边费用的相反数这是为了正确计算“反悔”操作带来的费用变化。这会导致图中存在负权边而Dijkstra算法不能直接处理负权图。SPFA可以处理负权虽然最坏复杂度高但在费用流这种特殊图每次增广只改变少量边上通常表现良好。我们需要修改边的结构体加入cost单位费用字段。同时在寻找增广路时我们不仅要记录到达每个点的最小费用dist还要记录路径的前驱边prevv和preve以便增广后能更新边的容量。struct MinCostEdge { int to; int rev; // 反向边在邻接表中的索引 long long cap; long long cost; // 单位流量的费用 }; class MinCostMaxFlow { private: int n; vectorvectorMinCostEdge graph; vectorlong long dist; vectorint prevv, preve; // 前驱节点和前驱边 const long long INF 1e18; public: MinCostMaxFlow(int node_count) : n(node_count), graph(node_count) {} void add_edge(int from, int to, long long cap, long long cost) { // 正向边 graph[from].push_back((MinCostEdge){to, (int)graph[to].size(), cap, cost}); // 反向边初始容量为0费用为-cost graph[to].push_back((MinCostEdge){from, (int)graph[from].size() - 1, 0, -cost}); } // 最小费用流返回 (最小费用, 最大流) pairlong long, long long min_cost_flow(int s, int t, long long maxf INF) { long long flow 0, cost 0; // 使用SPFA寻找最小费用路径 while (flow maxf) { dist.assign(n, INF); dist[s] 0; bool inqueue[n]; memset(inqueue, 0, sizeof(inqueue)); queueint q; q.push(s); inqueue[s] true; // SPFA 过程 while (!q.empty()) { int u q.front(); q.pop(); inqueue[u] false; for (int i 0; i (int)graph[u].size(); i) { MinCostEdge e graph[u][i]; if (e.cap 0 dist[e.to] dist[u] e.cost) { dist[e.to] dist[u] e.cost; prevv[e.to] u; preve[e.to] i; if (!inqueue[e.to]) { q.push(e.to); inqueue[e.to] true; } } } } if (dist[t] INF) { break; // 无法再找到增广路 } // 沿着找到的路径增广尽可能多的流 long long d maxf - flow; for (int v t; v ! s; v prevv[v]) { d min(d, graph[prevv[v]][preve[v]].cap); } flow d; cost d * dist[t]; // 本次增广的费用 流量 * 路径总单位费用 // 更新残余网络 for (int v t; v ! s; v prevv[v]) { MinCostEdge e graph[prevv[v]][preve[v]]; e.cap - d; graph[v][e.rev].cap d; } } return {cost, flow}; } };4.2 算法流程与费用计算逻辑SPFA找最短路以边的单位费用作为路径权重寻找从源点s到汇点t的、且剩余容量大于0的路径中总费用最小的那条。dist[t]就是这条路径的单位流量总费用。确定增广流量沿着找到的路径从汇点t回溯到源点s找出路径上所有边剩余容量的最小值d。这就是本次能增广的流量。更新流量和费用总流量flow增加d。总费用cost增加d * dist[t]。这是算法的核心保证了每次增加的都是“当前状态下”单位费用最小的流量。更新残余网络和Dinic一样对路径上的每条边减少其容量d并增加其反向边的容量d。关键点在于反向边的费用是负的。为什么假设我们有一条边u-v容量5费用3。我们推送了1单位流量。正向边容量变为4。我们创建或增加了一条反向边v-u容量为1费用为-3。这意味着如果后续的增广路使用了这条反向边v-u就相当于“退回了”之前从u-v流过的1单位流量。这1单位流量当初产生了3的费用现在“退回”它自然应该在总费用中扣除3所以反向边的费用是-3。这个设计完美地保证了费用计算的正确性。实操中的关键细节SPFA的判负环在纯最短路问题中SPFA需要判断负环。但在费用流中由于每次增广后图的结构改变反向边产生通常不会出现无限循环的负环。所以我们的实现省略了负环判断更简洁。但在极端构造的数据下理论上可能存在性能问题这时就需要更高级的势函数Dijkstra方法。prevv和preve数组它们的大小必须是节点数n。prevv[v]记录到达节点v的路径上的前驱节点preve[v]记录的是从前驱节点prevv[v]的邻接表中具体是哪条边通向v的索引。这个设计是为了能快速定位到边对象并进行更新。费用溢出和容量一样总费用也可能很大务必使用long long。最大流限制min_cost_flow函数中的maxf参数允许你指定一个期望的最大流。如果只要求最小费用而不要求一定是最大流可以传入一个较小的值。默认INF表示一直增广直到无法继续。5. 性能优化与高级技巧从SPFA到Primal-Dual基础的SPFA费用流已经能解决很多问题但当图很大或者边权变化复杂时SPFA可能成为瓶颈。工业级的实现和高端竞赛中更常用的是Primal-Dual原始对偶算法它使用势函数Potential将所有边权变为非负从而允许使用更快的Dijkstra算法来寻找最短增广路。5.1 势函数Potential的原理势函数h[v]为每个节点赋予一个势能。对于一条边u-v定义其缩减费用Reduced Cost为e.cost h[u] - h[v]。神奇的是如果我们能维护一组势函数使得对于残余网络中的所有边其缩减费用都非负那么我们就可以在这个“改造后”的图上运行Dijkstra算法来求最短最小费用路径。初始时可以设置h[v] 0或者用一次SPFA求出初始最短路作为初始势。每次用Dijkstra求出基于缩减费用的最短路径dist后我们不仅用这条路径增广还要更新势函数h[v] dist[v]。这个更新规则能保证缩减费用始终保持非负。5.2 Primal-Dual 算法实现框架下面是基于势函数和Dijkstra的MinCostMaxFlow实现概要。它比纯SPFA版本更复杂但最坏情况下的时间复杂度更有保障。class MinCostMaxFlowPD { private: struct Edge { int to, rev; long long cap, cost; }; int n; vectorvectorEdge graph; vectorlong long potential, dist; vectorint prevv, preve; const long long INF 1e18; // 使用Dijkstra寻找最小费用路径基于缩减费用 bool dijkstra(int s, int t) { dist.assign(n, INF); using P pairlong long, int; priority_queueP, vectorP, greaterP pq; dist[s] 0; pq.emplace(0, s); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (dist[u] d) continue; // 旧的、无效的距离值 for (int i 0; i (int)graph[u].size(); i) { Edge e graph[u][i]; if (e.cap 0) continue; // 关键使用缩减费用 long long nd dist[u] e.cost potential[u] - potential[e.to]; if (dist[e.to] nd) { dist[e.to] nd; prevv[e.to] u; preve[e.to] i; pq.emplace(nd, e.to); } } } return dist[t] ! INF; } public: MinCostMaxFlowPD(int node_count) : n(node_count), graph(node_count), potential(node_count, 0) {} void add_edge(int from, int to, long long cap, long long cost) { graph[from].push_back({to, (int)graph[to].size(), cap, cost}); graph[to].push_back({from, (int)graph[from].size() - 1, 0, -cost}); } pairlong long, long long min_cost_flow(int s, int t, long long maxf INF) { long long flow 0, cost 0; // 可选用一次SPFA初始化势函数以处理初始负权边。 // 如果保证初始图无边权为负可以跳过。 // initialize_potential(s); while (flow maxf dijkstra(s, t)) { // 更新势函数 for (int i 0; i n; i) { if (dist[i] INF) potential[i] dist[i]; // 对于不可达点势函数保持不变或可设为INF } long long d maxf - flow; for (int v t; v ! s; v prevv[v]) { d min(d, graph[prevv[v]][preve[v]].cap); } flow d; cost d * (potential[t] - potential[s]); // 注意这里实际费用计算 for (int v t; v ! s; v prevv[v]) { Edge e graph[prevv[v]][preve[v]]; e.cap - d; graph[v][e.rev].cap d; } } return {cost, flow}; } };关键点解析费用计算在更新势函数后从s到t的实际路径费用等于(potential[t] - potential[s])而不是dist[t]。因为dist中存储的是缩减费用。这是一个常见的易错点。初始化势函数如果初始图中就存在负权边直接运行Dijkstra会出错。此时需要用一次SPFA或Bellman-Ford计算出初始的最短距离并将其作为初始势potential。代码中的initialize_potential(s)函数就是做这个的。如果题目保证初始边权非负可以省略。性能对比对于稠密图或精心构造的使SPFA变慢的数据Primal-Dual算法优势明显。但对于随机数据或稀疏图两者差距可能不大。SPFA版本代码更短更易于理解和调试通常是首选的实现方式。5.3 其他实用优化技巧多路增广Dinic思想融入费用流类似于Dinic我们也可以在费用流中先做一次BFS或Dijkstra进行分层然后在分层图上进行DFS多路增广。这可以减少最短路算法的调用次数在某些图上特别是容量较小而费用简单的图有奇效。这种算法有时被称为zkw费用流一种基于Dinic分层和DFS的费用流算法。但实现更复杂且并非在所有情况下都优于SPFA/Primal-Dual。容量缩放对于容量非常大的边可以借鉴最大流算法中的容量缩放思想从高位到低位逐步确定流量。在费用流中应用相对较少但在特定场景下有用。图的存储优化如果节点数非常多1e5使用vectorvectorEdge可能会有一定的缓存不友好问题。可以考虑用单一的边数组vectorEdge edges和每个节点的出边索引列表vectorint head[N]的“前向星”存图方式这在纯最大流中很常见但在需要频繁通过e.rev找反向边的费用流中实现起来稍显繁琐。6. 实战应用与调试案例分析与常见问题理论说得再多不如实际跑一跑。我们用一个经典问题来串联整个实现并分享调试中常见的“坑”。6.1 实战案例运输问题建模与求解假设有两个仓库A、B三个市场1、2、3。仓库A有货物50吨B有70吨。市场1、2、3分别需要30、40、60吨。运输路线及单位运费元/吨如下A-1: 10元运力无限A-2: 8元 运力无限A-3: 12元运力无限B-1: 9元 运力无限B-2: 11元运力无限B-3: 7元 运力无限求满足所有市场需求的最小总运费。建模节点源点s(0)仓库A(1)仓库B(2)市场1(3)市场2(4)市场3(5)汇点t(6)。共n7个节点。边s-A: 容量50费用0s-B: 容量70费用0A-市场1,2,3: 容量INF费用分别为10, 8, 12B-市场1,2,3: 容量INF费用分别为9, 11, 7市场1,2,3-t: 容量分别为30, 40, 60费用0求解我们调用MinCostMaxFlow的min_cost_flow函数目标流量应为304060130总需求。如果最大流小于130说明供不应求无解。否则返回的费用就是最小总运费。int main() { // 节点数s, A, B, m1, m2, m3, t 共7个 MinCostMaxFlow mcmf(7); int s 0, A 1, B 2, m1 3, m2 4, m3 5, t 6; const long long INF 1e18; // 源点到仓库 mcmf.add_edge(s, A, 50, 0); mcmf.add_edge(s, B, 70, 0); // 仓库到市场 mcmf.add_edge(A, m1, INF, 10); mcmf.add_edge(A, m2, INF, 8); mcmf.add_edge(A, m3, INF, 12); mcmf.add_edge(B, m1, INF, 9); mcmf.add_edge(B, m2, INF, 11); mcmf.add_edge(B, m3, INF, 7); // 市场到汇点 mcmf.add_edge(m1, t, 30, 0); mcmf.add_edge(m2, t, 40, 0); mcmf.add_edge(m3, t, 60, 0); auto [cost, flow] mcmf.min_cost_flow(s, t); if (flow 130) { cout 无法满足所有需求最大流为 flow endl; } else { cout 最小总运费为 cost 元 endl; cout 总运输量为 flow 吨 endl; } return 0; }运行后算法会计算出最优的运输方案。你可以通过检查最终每条边的容量减少值即流量来得知具体的运输量。6.2 常见问题、调试技巧与排查清单即使有了模板在实际编码中还是会遇到各种问题。下面是我踩过的一些坑和解决方法。问题1程序运行结果错误费用或流量不对。检查容量和费用类型确保都是long long。int溢出是新手最常见错误。检查反向边费用务必是-cost。这是费用流正确性的核心。检查图的构建节点编号是否从0开始连续add_edge的参数顺序(from, to, cap, cost)是否正确特别是源点和汇点不要弄错。验证模型用一个小到可以手算的案例测试。比如两个节点一条边看看最大流和费用是否正确。问题2程序陷入死循环或超时。检查SPFA/循环条件在SPFA中确保inqueue标记被正确维护。在min_cost_flow循环中确保有跳出条件dist[t] INF。检查负环虽然费用流中不常见但如果数据构造特殊SPFA可能因负环而不终止。可以添加计数器如果某个节点入队次数超过n节点数次则可能存在负环应终止算法。对于Primal-Dual算法则要检查初始势函数的设置。INF值过大在dfs或确定增广流量d时如果INF设置得太大接近LLONG_MAX在运算min(f, e.cap)时如果e.cap也是一个很大的数可能导致加法溢出变成负数。将INF设置为一个安全的大数如1e18。当前弧优化重置在Dinic中每次BFS后必须重置iter数组。忘记重置会导致算法提前终止得不到最大流。问题3如何输出具体的流方案算法结束后图中每条正向边(u-v)的初始容量original_cap减去剩余容量e.cap就是这条边上流过的流量。你可以在add_edge时将边的初始容量也存储下来例如在Edge结构体中加一个original_cap字段或者在添加边后用一个单独的数据结构记录初始图。求解完毕后遍历所有边计算flow_on_edge original_cap - current_cap。对于流量大于0的边输出u, v, flow_on_edge。问题4面对复杂问题建模没有思路怎么办识别“流”什么是在网络中流动的东西任务、货物、人员、数据识别“源”和“汇”流的起点和终点是什么识别“节点”和“边”节点代表状态、位置或决策点。边代表转移、运输或分配的可能性其容量限制流量费用代表成本。善用“拆点”这是解决节点容量、时间分层、状态转移问题的万能钥匙。如果一个节点有通过限制就拆成“入点”和“出点”中间连一条容量为限制的边。从简单开始先尝试构建一个最简模型再逐步添加约束。很多复杂问题都是经典模型如二分图匹配、任务分配、运输问题的变种。调试清单[ ] 所有int是否已改为long long容量、费用、距离、流量[ ] 反向边的容量是否为0费用是否为-cost[ ] 节点编号是否在[0, n-1]范围内n的值是否正确[ ] SPFA/Dijkstra中是否只考虑了cap 0的边[ ] 在更新残余网络时是否同时更新了正向边和反向边[ ]INF的值是否设置得合理足够大且不会在运算中溢出[ ] 如果需要输出方案是否记录了初始容量网络流和费用流的代码就像一把精密的瑞士军刀每个细节都关乎正确性。第一次实现时建议严格按照模板来写并通过大量练习来熟悉建模和调试。一旦掌握你会发现它能优雅地解决许多看似棘手的优化问题。从竞赛到工程这套思想的价值远超代码本身。
)
![[具身智能-634]：Python 封装的地平线 VIO 多媒体库：libsrcampy库详解](http://pic.xiahunao.cn/yaotu/[具身智能-634]：Python 封装的地平线 VIO 多媒体库：libsrcampy库详解)
