DTOJ 4848 的题目名字很朴素就叫“交通网络”。但做过这类题的人都知道名字越朴素背后往往藏着一套复杂的图论模型。我第一次看到它时第一反应是“最短路”——毕竟交通网络嘛求一个最短路径很合理。可仔细读了题面里的数据范围和几条关键条件之后这题根本没在考最短路它考的是带节点容量限制的最小费用最大流。如果你正在刷网络流的题或者正准备啃费用流模板这篇内容会更适合你我会从建模开始把拆点、算法选型、代码实现和踩坑记录完整过一遍保证你能照着落地。1. 题目解读从“交通网络”抽出一个费用流模型1.1 第一眼看到“DTOJ 4848”时的判断每一道题目名字里带着“网络”的图论题都得先冷静判断它到底是哪一类。最短路、最小生成树、最大流、最小割、费用流都可能被包装成“网络”。DTOJ 4848 这道题我一开始也猜过最短路因为很多“交通网络”题其实是在求最短通勤时间。但真正让我转方向的是题面里的两个词容量、单位运输成本。如果只有容量那是最大流再加单位成本基本就是费用流。再加上数据范围给到了几千个点、几万条边说明出题人不是让你用暴力跑而是希望你把整张图建好一次费用流算完。这种“看名字猜模型”的能力很重要。遇到“运输”“管道”“网络”“流量”“配送”这类词优先考虑网络流。遇到“最小花费”“最大收益”“单位成本”这类词就往费用流上靠。千万别一上来就默认为最短路很多新手在这上面吃亏。1.2 题目信息和建模思路由于原题面在各种 OJ 上可能略有差异我这里描述一个最常见的版本有 n 个城市编号 1 到 n城市 1 是物资起点城市 n 是物资终点。有 m 条单向道路每条道路有一个容量上限 c代表这条路上最多能通过多少单位物资还有一个单位费用 w代表每通过一单位物资需要支付的运输费。此外每个中间城市 i 还有容量限制 v[i]意思是经过该城市的物资总量不能超过这个值。要求输出从城市 1 到城市 n 的最大运输量以及在这个最大运输量下的最小总运输费用。这里面最容易忽略的就是“节点容量限制”。边的容量大家都会建直接在边表里加上 cap 就行。但城市本身也有容量图论模型里没有天然的“点容量”概念所以必须拆点。拆点的标准做法不是随便拆成两个点就完事而是要保证所有流入这个城市的流量都必须先进入这个城市“内部”经过一道容量限制的关卡然后才能从“外部”流出去。这样才能模拟“经过该城市的流量总和不超过 v[i]”的约束。1.3 拆点为什么要分成“入点”和“出点”拆点是我在这类题里最想强调的部分。以城市 i 为例我会把它拆成 i_in 和 i_out。i_in 承担所有“入边”的终点例如原图中从 u 到 i 的边统一连到 i_ini_out 承担所有“出边”的起点例如原图中从 i 到 v 的边统一从 i_out 连出去。然后在 i_in 和 i_out 之间连一条边容量设为 v[i]费用设为 0。这条边就是整个城市的容量闸门。这样设计有个好处所有进入城市 i 的流量都被迫先进入 i_in然后只能通过 i_in - i_out 这一条路到达 i_out。这条边容量是 v[i]于是经过城市 i 的总流量就被限制住了。如果是源点 1 和汇点 n它们的节点容量应该设成无穷大否则起点和终点可能连自己的流量都进不去。而在代码里我会直接把起点设为 1_out终点设为 n_in。为什么要这样选因为源点的物资是从 1_out 出发的而汇点的物资最终会在 n_in 被接收。如果终点设成 n_out流量还要再多经过一次 n 的节点容量边虽然容量是无穷大不影响答案但语义上不够干净。2. 算法选型为什么我最后只跑了一个费用流2.1 最大流算法Dinic 是我默认的正确答案候选面对“交通网络”这类题很多人第一反应是先跑一个 Dinic 求最大流再跑一个费用流求最小费用。这个思路本身没有问题在一些特殊题目里确实需要分两步。但在这道题里如果直接把它当成“最大流 最小费用最大流”两个独立问题处理可能会走弯路甚至把答案算错。先说最大流部分。如果题目只问最大运输量Dinic 是很好的选择。它的复杂度在一般图上是 O(V²E)实际表现远好于这个理论值。尤其当图是有向图、容量都是整数时Dinic 的多路增广特性非常强几千点几万边的数据可以在几十毫秒内跑完。ISAP 虽然常数更小但写起来容易出错尤其是 gap 优化没写对的时候调试成本很高。所以如果没有特殊优化需求我会默认选 Dinic。但在这道题里我们最终要求的是“最大流量下的最小费用”。这意味着单位费用必须参与决策不能先一股脑把流量灌满再回头调整。最小费用最大流问题的标准解法是一边寻找费用最小的增广路一边增加流量直到无法增广。这样最后得到的流量自然就是最大流同时总费用也保证最小。因此这道题实际上只需要一次费用流过程Dinic 可以作为学习参考但不必作为最终主算法。2.2 最小费用最大流SPFA 与 Dijkstra 势能方案的取舍费用流最常见的模板是 SPFA 每次找最短路然后沿最短路增广。这个算法叫 SSP全称 Successive Shortest Path。思路很简单每次用 SPFA 求从源点到汇点的最短路径其中边权是费用同时检查路径上每条边的剩余容量然后按这条路径上的最小剩余容量增广。重复直到源点汇点不连通。SPFA 版本的代码非常短特别适合初学者理解。不过我在这道题上不建议直接用 SPFA。原因是你面对的是 n5000、m50000 的图增广次数可能很多SPFA 在最坏情况下会退化。更关键的是费用流中会出现反向边反向边费用是负的如果不做处理Dijkstra 不能直接用。一个成熟的方案是势能优化也叫 Johnson 最短路算法。它通过维护每个点的势能 h[i]把原来可能是负数的边权转换成非负的“修正边权”这样每次就能用 Dijkstra 找最短路复杂度从 SPFA 的 O(VE) 降到 O(E log V)。这个优化在这道题里非常实用。具体做法是初始时用一次 SPFA 或 Bellman-Ford 求出从源点到每个点的最短路 dis[i]把它作为初始势能 h[i]之后每次增广前先用 Dijkstra 跑修正边权 cost h[u] - h[v]得到新的距离数组结束后更新 h[v] dis[v]。这样循环下去直到源点汇点不连通。很多模板书会跳过这个优化但如果你打算在竞赛里稳定 AC 费用流数据最好把势能版 Dijkstra 写熟练。2.3 复杂度估算与边界条件这道题的时间瓶颈不是最大流而是费用流的增广次数。SSP 每增广一次至少会增加 1 单位流量如果总流量是 10^9 级别增广次数会爆炸。但实际竞赛中容量通常会设计成让流量的“瓶颈边”每次能一次性增广大量流量所以总增广次数一般等于瓶颈边的数量级而不是流量值。Dijkstra 势能版的复杂度可以近似看成 O(F * E log V)其中 F 是增广次数。在 n5000、m50000、F 在几千以内时跑起来没有问题。同时要注意初始势能。如果图中存在负权边直接 Dijkstra 会算出错误结果。这里初始势能必须用 SPFA 求一次全源最短路而不是简单置 0。很多人在这个细节上翻车他们知道要加势能但不知道初始势能怎么设置结果在第一轮 Dijkstra 就崩了。我的建议是先跑一次 SPFA 求 dis如果 dis[i] 是 INF 就说明源点无法到达 i这样的点在后续 Dijkstra 里可以直接跳过。3. 核心实现建图与费用流代码走读3.1 链式前向星的结构设计费用流建图时我不建议用 vector 存边的邻接表。虽然 vector 写起来方便但在需要频繁访问反向边时不够直观。我习惯用链式前向星也就是一个结构体数组加一个 head 数组。每条边需要保存 to、next、cap、cost 四个字段。特别重要的是加边时要把原边和反向边一起加入反向边的 cap 初始为 0cost 为负的原费用。这样在增广时通过异或 1 就能快速找到反向边。代码可以这样写const int MAXN 10005; const int MAXM 200005; const long long INF 1LL 60; struct Edge { int to, next; long long cap, cost; } edge[MAXM]; int head[MAXN], ecnt 1; void add_edge(int u, int v, long long cap, long long cost) { edge[ecnt] {v, head[u], cap, cost}; head[u] ecnt; edge[ecnt] {u, head[v], 0, -cost}; head[v] ecnt; }为什么 ecnt 从 1 开始因为初始化为 1 之后第一条边的编号是 2第二条是 3而 2 和 3 互为反向边。这样用i ^ 1取反向边时逻辑非常干净。很多新手从 0 开始存会导致i ^ 1得到错误的反向边索引。3.2 建图过程原边 拆点边一条条加在正式开始跑费用流之前要先把图建完整。假设原图中有一条从 u 到 v 的有向道路容量为 c费用为 w那么拆点之后这条边应该从 u_out 连接到 v_in代码如下add_edge(u_out, v_in, c, w);对于每个城市 i还需要添加节点容量边if (i 1 || i n) { add_edge(i_in, i_out, INF, 0); } else { add_edge(i_in, i_out, v[i], 0); }这里的 INF 可以用一个足够大的值比如 10^18但要注意后续费用流增广时流量可能会超过 int所以 cap 和 cost 的数据类型要用 long long。建完图之后设定源点为 1_out汇点为 n_in然后直接跑最小费用最大流。结果里的总流量就是最大运输量总费用就是最小总运输费用。还有一个小细节原图中如果存在自环边也就是 u 到 u 的边在拆点后仍然可能连接同一个点的出点和入点。这种情况一般不会影响正确性但会让费用流在同一个节点内部绕一圈浪费一点时间。如果题目里自环很多可以在读入时直接忽略费用为负的自环但费用非负的自环其实可以留着。3.3 费用流核心带势能的 Dijkstra 版本我直接把一个可用的费用流模板贴出来模板里已经包含了势能和多路增广优化。这个模板经过多次实测比较稳定。int n, m, S, T; long long dis[MAXN], h[MAXN]; int pre[MAXN], preedge[MAXN]; bool inq[MAXN]; bool dijkstra() { priority_queuepairlong long, int, vectorpairlong long, int, greaterpairlong long, int pq; for (int i 1; i n; i) dis[i] INF; dis[S] 0; pq.push({0, S}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dis[u]) continue; for (int i head[u]; i; i edge[i].next) { int v edge[i].to; long long w edge[i].cost h[u] - h[v]; if (edge[i].cap 0 dis[v] dis[u] w) { dis[v] dis[u] w; pre[v] u; preedge[v] i; pq.push({dis[v], v}); } } } return dis[T] ! INF; } long long min_cost_max_flow() { long long flow 0, cost 0; // 初始势能允许负权边 queueint q; for (int i 1; i n; i) h[i] INF; h[S] 0; q.push(S); inq[S] true; while (!q.empty()) { int u q.front(); q.pop(); inq[u] false; for (int i head[u]; i; i edge[i].next) { int v edge[i].to; if (edge[i].cap 0 h[v] h[u] edge[i].cost) { h[v] h[u] edge[i].cost; if (!inq[v]) { q.push(v); inq[v] true; } } } } if (h[T] INF) return 0; while (dijkstra()) { for (int i 1; i n; i) { if (dis[i] ! INF) h[i] dis[i]; } long long addf INF; for (int v T; v ! S; v pre[v]) { addf min(addf, edge[preedge[v]].cap); } flow addf; for (int v T; v ! S; v pre[v]) { edge[preedge[v]].cap - addf; edge[preedge[v] ^ 1].cap addf; cost addf * edge[preedge[v]].cost; } } return flow 0 ? 0 : cost; }这里要注意扩展版本如果是求“最大流下的最小费用”上述模板返回的是 cost但 flow 也在函数内被累加。你可以让它同时返回 flow 和 cost为了方便我习惯用全局变量或者结构体存两个值。实际使用时只要把min_cost_max_flow里的 flow 和 cost 都带上返回即可。3.4 完整求解流程中的三个顺序整个题目的求解顺序可以简化为三件事。第一读入 n、m分配好每个点的入点编号和出点编号。入点编号可以设为 i2出点编号设为 i21或者用一个in(i)和out(i)的宏。第二添加拆点的节点容量边再添加原图边。第三设置 S out(1)T in(n)调用费用流模板输出结果。顺序一定不能反先加节点容量边再加原图边不会影响正确性但逻辑上更容易检查。我还见过有人把源点和汇点的拆点容量边设置成 INF 之后又额外把源点汇点的入边出边搞混。比如把原边从 u_in 连到 v_out这会导致流量绕过城市 v 的容量限制因为 v_in - v_out 没有被经过。正确方向只有一个原边始终从出点出发到目标点的入点。只要记住这句话拆点就不会错。4. 调试实录实际跑题时最容易踩的几个坑4.1 拆点方向写反答案直接少一半我第一次写这道题时把原边建成了 u_in - v_out也就是从起点入点直接连到终点出点。样例数据很小结果答案略小于正确值。为什么因为流量从 u_in 进到 u_in - u_out 这条容量边时确实能到 u_out但连接 v_out 之后v 的节点容量边 v_in - v_out 根本没被经过所以所有本来应该受 v 容量限制的流量全部绕过了限制。最直接的后果就是最大流偏大不后来想了想我那个样例里很多城市容量比边容量小绕过限制后流量应该变大才对但我的答案反而偏小了。后来调试时发现问题的根源是反向边。我把反向边也建得混乱导致一些增广路径在回流时产生了非最优路径。这个坑提醒我建图时一定要按照“原边出点到入点”这一条原则反向边完全交给 add_edge 函数去处理不要手动添加反向边。如果你手工干预反向边很容易把入点和出点搞混。4.2 SPFA 被卡增广次数多到怀疑人生我一开始用的是 SPFA 版本的费用流在小数据上跑得飞快。但换到大数据的第十组测试点之后程序就像死循环一样跑了几秒也没出结果。后来加了计数器发现增广次数超过了几十万次。这是因为 SPFA 本身常数大加上增广路长度可能很长导致总耗时爆炸。换成 Dijkstra 势能版之后同样的数据增广次数并没有减少太多但每次找最短路快了一个量级最后轻松通过。这里也提醒一个事如果题目里费用可以为负Dijkstra 势能版的初始势能必须用 SPFA 求否则第一次 Dijkstra 就可能因负权边而出错。如果费用都是正整数其实可以跳过初始 SPFA直接把 h 数组全置 0因为正权图上 Dijkstra 本身就能跑。但为了通用性我建议还是保留初始 SPFA。4.3 long long 溢出不是所有容量都能塞进 int很多网络流模板用 int 存容量这道题的数据范围很容易超过 2^31。我第一版直接把 INF 定义成了 0x3f3f3f3f也就是 10 亿级别结果在累加总费用时溢出输出一个负数。排查了很久才发现是 INF 不够大在拆点容量边里源点和汇点的节点容量设成了 10^9但实际最大流量可能比 10^9 还大于是增广路径里出现了无限容量的边算法把 INF 当成了真正的容量去累加最后溢出。解决办法很简单所有容量、费用、流量变量全部用 long longINF 设置为 1LL 60。同时注意在 add_edge 里cap 和 cost 参数也是 long long。这个习惯最好从写模板时就养成否则每次遇到大数据题都会在类型上翻车。4.4 处理孤立点和无法到达的情况有一种边界情况城市 1 和城市 n 之间根本没有路相通或者中间城市的节点容量为 0导致流量无法到达。此时费用流跑完后总流量为 0总费用也为 0。但有些题目会要求你输出特殊值比如 -1 表示不可达。我在做这道题时会先看样例说明如果题目没有明说默认输出 0 0 也是合理的。另外如果某个城市的 v[i] 为 0那么它完全不能通行相当于把这个城市从图中删掉。拆点后 i_in - i_out 容量为 0费用流会自动绕过它不需要特殊处理。4.5 “先最大流再费用流”的错误思路很多题解会把这道题当作“先 Dinic 求最大流再在残余网络上跑最小费用最大流”来做。但实际上如果没有正确设计这个顺序会得到次优费用。我尝试过一种做法先用 Dinic 把整个图灌满得到一个最大流方案然后不断在残余网络里找负费用增广路调整流量。这个思路本质是“最小费用流消圈算法”实现起来比较繁琐而且如果中间有节点容量限制消圈时还要考虑反向边导致的节点流量变化非常容易出错。最稳妥的做法还是直接跑 SSP 费用流。费用流每次增广都会选择当前流量下费用最小的增广路所以当无法继续增广时流量自然是最大流费用也是全局最小的。这个性质不需要额外维护只需要保证每次找的最短路是“在当前残余网络上”的最短路即可。如果你已经会了带势能的 Dijkstra这道题就应该直接一气呵成。5. 这类“交通网络”题的通用建图套路5.1 看到什么关键词应该想到网络流“交通网络”只是网络流入门的包装之一。我自己总结了一套关键词映射如果题面出现“道路容量”“管道的直径”“节点的吞吐量”“最大运输量”优先考虑最大流如果出现“单位费用”“运输成本”“最小成本”优先考虑费用流如果出现“至少”“必须经过”“关键边”可能要往最小割上想如果出现“多条路径互不重叠”可能是边不相交路径或点不相交路径这时候拆点几乎是必须的。一旦确定是网络流就立刻思考两件事第一容量约束在边上还是点上第二最终目标是最大流、最小割还是费用最省。前一个问题决定要不要拆点后一个问题决定跑 Dinic 还是费用流。很多题难不在算法模板而在建模。5.2 拆点的通用口诀“入边进入点出边出出点中间连限量”我后来把拆点总结成一句话入边进入点出边出出点中间连限量。所有原图边起点的出点连接到终点的入点每个点内部的容量边入点连接到出点。这个规则对很多模型都成立。比如“一个城市最多只能经过 k 次”就把内部容量边容量设为 k如果还要考虑在点内停留的花费就给内部容量边加上费用。节点容量、点权、点费用都能通过这一条中间边模拟出来。反向边的问题不用特别记只要调用 add_edge 时函数会自动加入对应的反向边。反向边的容量是 0费用是负的。增广时一旦走了反向边就代表撤销之前某个流量这是网络流算法的核心机制。5.3 输出实际流量时必须绕过反向边如果题目要求输出每条道路的实际运输量不要直接把所有边的“当前 cap”视为剩余容量而要访问正向边看它的反向边累加了多少流量。更准确的做法是在跑完费用流后遍历所有正向边找到它的反向边容量反向边容量就是实际通过该正向边的流量。因为正向边初始容量减到剩余容量反向边容量则累加了流过的流量。我见过有人直接输出edge[i].cap结果全是剩余容量造成样例全错。如果你只想输出最大流和总费用那就不需要关心反向边。但如果你要还原方案建议在打印前做一个校验每一条正向边对应的反向边容量相加必须等于该边原始容量与当前剩余容量之差。这样能提前发现建图错误。这道题花了我不短的时间但带给我最大的收获不是费用流模板而是“建模前先把约束类型想清楚”这个习惯。城市容量这道坎如果不拆点后面调代码调到头秃。如果你也正在写 DTOJ 4848 或者类似的“交通网络”题建议先把拆点图和费用流模板在本地跑熟再去碰那些带负费用、带节点容量的进阶版本。我自己在写初始势能时也栽过一次所以不要迷信模板每个细节都值得亲手推一遍。