1. 项目概述从“深海机器人”到“最大费用流”的建模之旅看到“洛谷·[网络流24题]深海机器人问题”这个标题很多刚接触网络流的同学可能会有点懵。深海机器人听起来像是某种海洋探测的高科技项目怎么和算法竞赛里的网络流扯上关系了这正是网络流建模的魅力所在——它将一个看似复杂的、带有故事背景的实际问题抽象成一个纯粹的图论模型然后用成熟高效的算法一击即破。简单来说这道题描述了一个这样的场景在深海的某个区域有一个由网格点构成的“海底矿区”每个网格边即连接两个相邻点的路径上散布着不同价值的“标本”。我们拥有多支机器人小队每支小队有指定数量的机器人需要从不同的起点出发前往不同的终点。机器人在沿着网格边移动时可以采集该边上的标本并获得其价值。但这里有个关键限制每条边上的标本数量是有限的即一条边被一个机器人采集后其价值对于后续的机器人可能减少或消失。我们的目标是规划所有机器人的行进路线使得采集到的标本总价值最大。如果你熟悉网络流尤其是费用流此刻可能已经会心一笑了。这不就是一个典型的“多源多汇”、“边有容量和费用”的最大费用最大流问题吗没错这道题的经典之处就在于它完美地诠释了如何将一个带有“资源竞争”和“路径规划”元素的题目转化为网络流模型。通过这道题你不仅能学会费用流的应用更能掌握一种将具体问题抽象为流网络的核心思维。接下来我将带你彻底拆解这个模型从思路构建到代码实现最后分享一些我调试这类题目时积累的独家心得。2. 核心思路拆解如何将海底网格变成一张流网络面对任何网络流建模题第一步也是最关键的一步就是确定网络中的“流”到底代表什么。在这个问题里流很自然地代表了在海底移动的机器人。我们的目标是让尽可能多的机器人流从各自的起点源点移动到各自的终点汇点并在移动过程中经过那些带有价值的边产生费用同时遵守每条边上标本数量的限制边的容量。2.1 节点与边的设计模型构建的核心在于对原问题网格图的处理。通常题目给出的海底区域是一个P x Q的网格。一种直观的想法是把每个网格点当作网络中的节点。但这样会有一个问题标本是分布在边上的而不是在点上。因此我们需要通过“点拆边”或“边化点”的技巧来处理。最经典且高效的建模方法如下节点将每一个网格坐标(i, j)直接映射为一个唯一的节点编号。例如对于坐标(i, j)其节点编号可以是idx i * Q j假设行列从0开始。这样我们就有P * Q个节点。边代表移动与采集这是建模的精髓。对于原网格中的一条有向边比如从(i, j)到(i, j1)的向东边我们在流网络中建立两条有向边第一条边采集边容量为1费用为该边上的标本价值。这条边代表一个机器人第一次经过这条边并成功采集了标本获得了全部价值。因为标本被采集后就没了所以容量为1。第二条边通行边容量为无穷大或一个足够大的数如题目给出的机器人总数费用为0。这条边代表后续的机器人再经过这条边但已经无标本可采所以不产生价值。为什么是两条边这是为了区分“有收益的通行”和“无收益的通行”。网络流算法在寻找增广路时会优先选择费用高的边对于最大费用流。因此算法会尽量让流机器人走那些还有容量且费用高即还有标本的边。当那条边的容量用尽后流就只能走费用为0的边通行完美模拟了标本被采集一次后失效的设定。超级源点与超级汇点由于我们有多个起点机器人出发地和多个终点机器人目的地这是典型的多源多汇问题。标准网络流算法处理的是单源单汇。解决方法就是引入一个超级源点S和一个超级汇点T。从超级源点S向每个实际的起点(x, y)连一条边容量为该起点处机器人的数量k费用为0。这表示从这里提供了k个单位的“流”机器人。从每个实际的终点(x, y)向超级汇点T连一条边容量为该终点处需要接收的机器人数量k注意题目描述有时是到达即可有时是要求特定数量费用为0。这表示流到这里就被吸收了。2.2 最大费用最大流算法选择模型建好后我们需要一个算法来计算从S到T的流在满足容量限制的前提下使得总费用最大。这就是最大费用最大流问题。最常用的方法是SPFA或Bellman-Ford实现的连续最短路算法。为什么是SPFA而不是Dijkstra因为图中存在费用为负的边吗不在这个模型里所有边的费用标本价值都是非负的。但是当我们将其转化为最小费用最大流来求解时需要将边权取反。也就是说我们建立网络时边的费用w是标本的正价值但为了套用经典的最小费用流算法我们会将每条边的费用设置为-w。这样求最小费用流就等价于求原问题的最大费用流。而一旦引入负权边Dijkstra算法就无法直接使用了除非使用Johnson重标价或势能Dijkstra。对于竞赛编程使用SPFA来实现最小费用流是最简单、最不容易出错的尽管在最坏情况下复杂度较高但本题数据规模通常足以应付。算法流程简述以费用为边权此时已取反即-w在残留网络上不断寻找从S到T的最短增广路即单位花费最小的路径。找到后计算这条路径上能通过的最大流量flow即路径上所有边剩余容量的最小值。将flow单位的流推送到这条路径上并更新残留网络正向边容量减少flow反向边容量增加flow。累加总费用cost flow * dist[T]注意这里的dist[T]是取反后的最短路径长即-原收益所以累加的是负值。重复步骤1-4直到无法找到增广路为止。最终-cost就是我们想要的最大总收益。3. 代码实现与关键细节解析理论清晰后我们来看代码实现。我会以C为例并着重讲解几个容易出错的细节。3.1 数据结构定义首先定义边的结构体和网络流类。这里采用链式前向星存图方便处理反向边。#include bits/stdc.h using namespace std; const int MAXN 1000; // 根据题目网格最大尺寸调整P*Q 2 const int MAXM 10000; // 边数估计每个网格点最多4条边每条原边拆成2条网络边 const int INF 0x3f3f3f3f; struct Edge { int to, next, cap, cost; // 指向节点下一条边索引容量费用这里是取反后的费用 }; class MCMF { public: int head[MAXN], cnt; Edge edges[MAXM * 2]; // 注意要开两倍因为要存反向边 int dist[MAXN], pre[MAXN], incf[MAXN]; bool inq[MAXN]; MCMF() { memset(head, -1, sizeof(head)); cnt 0; } void addEdge(int u, int v, int cap, int cost) { // 加正向边 edges[cnt] {v, head[u], cap, cost}; head[u] cnt; // 加反向边 edges[cnt] {u, head[v], 0, -cost}; // 反向边初始容量为0费用为-cost head[v] cnt; } bool spfa(int s, int t) { memset(dist, 0x3f, sizeof(dist)); memset(inq, 0, sizeof(inq)); queueint q; q.push(s); dist[s] 0; inq[s] true; incf[s] INF; // 源点流量无限 while (!q.empty()) { int u q.front(); q.pop(); inq[u] false; for (int i head[u]; ~i; i edges[i].next) { int v edges[i].to, cap edges[i].cap, cost edges[i].cost; if (cap 0 dist[v] dist[u] cost) { dist[v] dist[u] cost; pre[v] i; // 记录前驱边 incf[v] min(incf[u], cap); if (!inq[v]) { q.push(v); inq[v] true; } } } } return dist[t] ! INF; // 汇点可达 } // 返回最大流和最小费用 pairint, int solve(int s, int t) { int maxflow 0, mincost 0; while (spfa(s, t)) { int flow incf[t]; maxflow flow; for (int u t; u ! s; u edges[pre[u] ^ 1].to) { int i pre[u]; edges[i].cap - flow; edges[i ^ 1].cap flow; // 利用异或1操作找到反向边 } mincost flow * dist[t]; } return {maxflow, mincost}; } };3.2 建图过程详解这是整个代码的核心必须严格对应之前的建模思路。int main() { int A, B; // A条纵向边向北B条横向边向东这里需要仔细看题通常是先列数再行数 int P, Q; // P行Q列 cin A B P Q; // 注意洛谷原题输入格式可能是先给A,B再给P,Q。且坐标描述可能从(0,0)或(1,1)开始。 // 我们统一将网格点(i,j)编号为 i*(Q1) j。因为P行Q列的网格有(P1)行点和(Q1)列点。 // 这里假设输入是P1行Q1列的点阵题目给出的是边的信息。 // 我们按(P1)*(Q1)个点来算。 int N (P1) * (Q1); // 总网格点数 int S N, T N 1; // 超级源点和汇点 MCMF mcmf; // 第一步读入横向边东向的标本价值 for (int i 0; i P; i) { for (int j 0; j Q; j) { // 横向有Q条边 int val; cin val; int u i * (Q1) j; int v u 1; // 向东移动列号1 // 添加两条边一条容量1费用为-val用于采集一条容量INF费用0用于通行 mcmf.addEdge(u, v, 1, -val); mcmf.addEdge(u, v, INF, 0); } } // 第二步读入纵向边北向的标本价值 for (int j 0; j Q; j) { for (int i 0; i P; i) { // 纵向有P条边 int val; cin val; int u i * (Q1) j; int v u (Q1); // 向北移动跳到下一行 mcmf.addEdge(u, v, 1, -val); mcmf.addEdge(u, v, INF, 0); } } // 第三步处理机器人的起点和终点 for (int i 0; i A; i) { int k, x, y; cin k x y; // k个机器人从(x,y)出发 int node_id x * (Q1) y; // 计算节点编号注意输入坐标可能从0或1开始需调整 mcmf.addEdge(S, node_id, k, 0); } for (int i 0; i B; i) { int k, x, y; cin k x y; // k个机器人需要到达(x,y) int node_id x * (Q1) y; mcmf.addEdge(node_id, T, k, 0); } auto [maxflow, mincost] mcmf.solve(S, T); cout -mincost endl; // 输出最大收益 return 0; }关键细节解析坐标转换与节点编号这是最容易出错的地方。题目输入的P和Q有时代表“网格数”有时代表“点数”。必须仔细阅读题目描述。通常“深海机器人问题”中P和Q表示海底区域的大小那么就有(P1) * (Q1)个网格点。节点编号公式id i * (Q1) j确保了每个点有唯一ID。务必自己画一个2x3的网格验证一下编号是否正确。边的方向题目通常规定机器人只能向东或向北移动从西南角到东北角。因此我们只建了从(i,j)到(i, j1)和到(i1, j)的边。如果你的图需要双向移动则需要对两个方向都建边。容量INF的设置通行边的容量理论上可以是任何大于等于最大可能流量的值。通常直接设为一个很大的数比如1e9或0x3f3f3f3f。在代码中我用了INF但要注意INF在费用流算法中通常用于距离初始化这里用作容量可能混淆。最好单独定义一个BIG常量。费用取反在addEdge时采集边的费用传入的是-val。这是为了后续调用最小费用流算法。最终答案需要再取反-mincost。4. 调试技巧与常见问题排查即便思路和代码都写出来了网络流题目依然可能因为一些隐蔽的错误导致WA错误答案或TLE超时。以下是我在刷题和比赛中总结的排查清单。4.1 常见WA原因建图错误占90%以上节点编号算错这是头号杀手。用一个小样例比如2x2网格打印出每个坐标(i,j)对应的节点编号id手动模拟一下边的连接看是否符合预期。边数开太小每条原边要拆成2条网络边每个机器人起终点要连2条边正向和反向。反向边也要算进去如果使用链式前向星MAXM至少要是预估边数的2倍。开小了会导致越界、数据覆盖产生各种灵异错误。容量或费用设错采集边的容量一定是1吗如果一条边上的标本可以被多个机器人采集容量就要相应增加。通行边的费用一定是0吗确认无误。超级源汇连接错误检查从S连向起点的边容量是否为机器人数量k从终点连向T的边容量是否为需要接收的数量k。方向别反了。算法实现细节SPFA判环与负环理论上由于我们加入了反向边费用为-cost在残留网络中可能存在负环。但标准的最小费用流算法连续最短路要求初始网络无负环且每次在最短增广路上增广不会引入新的负环。所以使用SPFA求最短路是安全的。但如果你的图本身建模有误造成了负环SPFA可能会死循环。可以增加计数器限制松弛次数。费用溢出总费用mincost可能很大需要使用long long。INF也要用0x3f3f3f3f3f3f3f3f。4.2 性能优化与TLE应对本题数据规模通常不会太大但如果你遇到TLE或者想写出更稳健的代码可以考虑以下几点使用势能DijkstraPrimal-Dual这是最小费用流的标准高效算法。它通过引入“势能”h[v]将原图所有边权变为非负从而可以使用更快的Dijkstra算法求最短路。虽然代码稍复杂但性能稳定尤其适合边权非负或经过处理后非负的图。对于本题所有原始边权标本价值非负取反后为负但可以通过初始势能比如用一次SPFA计算将其调整为非负。// 势能更新对于每条边(u,v)新的边权 w w h[u] - h[v] // 在每次Dijkstra后更新势能h[v] dist[v]实现Primal-Dual算法能有效避免SPFA的不稳定最坏情况。检查边数如果P和Q较大比如几百网格边数会达到O(P*Q)级别再乘以2双向采集/通行边数可能达到几十万。确保你的MAXM常量足够大。输入优化使用scanf或ios::sync_with_stdio(false)加速C的输入输出。4.3 个人调试心得从小样例开始不要一上来就跑题目的完整样例。自己构造一个最小的、能手动计算结果的例子。比如一个1x2的网格只有一条横向边上有价值为5的标本一个机器人从(0,0)到(0,1)。手动算最大收益是5。然后用你的程序跑看输出是不是5。如果不是用调试器或打印中间图结构如每个点的出边来查。可视化工具对于复杂的建图可以在调试时写一个简单的函数将S、T和所有节点、边的容量费用打印出来。虽然繁琐但一次成功的可视化调试能帮你彻底理解模型。理解“流”的路径在调试时可以尝试在spfa找到增广路后打印出这条路径上的节点。看看机器人实际是怎么走的是否符合你的预期。这能帮你发现建图方向错误等问题。关注“多组数据”洛谷的题目可能是多组测试数据虽然本题通常不是。如果你的代码跑多组数据一定要记得初始化MCMF类的head数组、cnt计数器必须在每组数据开始前清零。5. 模型扩展与思维提升“深海机器人问题”是网络流24题中非常经典的一道它代表了一类“资源竞争型路径规划”问题。掌握它你就掌握了一把钥匙。我们可以看看这个模型还能解决哪些变种问题多次采集问题如果一条边上的标本可以被采集多次比如最多k次那么只需要将“采集边”的容量从1改为k即可。通行边容量依然是INF。不同机器人价值不同如果不同种类的机器人采集同一标本获得的价值不同这就变成了一个“多商品流”问题建模会复杂很多可能需要对边进行进一步拆分或使用其他技巧。带有“时间”或“顺序”的采集如果标本价值会随时间衰减或者机器人有先后顺序这通常需要结合分层图时间拆点等技术。从最大费用流到最小费用流很多题目是求最小成本例如运输问题。其本质完全相同只是边费用代表成本我们直接求最小费用最大流即可无需取反。这道题的精髓在于“一条边拆成两条”来区分有收益的首次使用和无收益的后续使用。这种思想在诸如“软件安装依赖”、“任务调度”等问题中也有体现。当你遇到一个问题其中某些“资源”或“通道”在首次被占用时会产生效益或成本而重复占用则效益不同或成本变化时就应该立刻想到这个模型。最后网络流的学习离不开大量的练习和总结。每做一道题不仅要AC更要问自己这个问题的“流”是什么“容量”限制了什么“费用”又代表了什么源和汇是如何设置的只有把建模过程像解数学题一样清晰地写下来才能真正内化这种强大的抽象思维能力。这道“深海机器人问题”就是一个绝佳的起点它干净利落地展示了如何将生动的故事背景转化为严谨优美的图论模型并用算法高效求解。希望这篇详细的拆解能帮你打通任督二脉在网络流的学习道路上走得更稳更远。如果在实现过程中遇到其他坑点不妨回头再看看建图部分十有八九问题就出在那里。 网络流建模实战：从深海机器人问题解析最大费用流算法
1. 项目概述从“深海机器人”到“最大费用流”的建模之旅看到“洛谷·[网络流24题]深海机器人问题”这个标题很多刚接触网络流的同学可能会有点懵。深海机器人听起来像是某种海洋探测的高科技项目怎么和算法竞赛里的网络流扯上关系了这正是网络流建模的魅力所在——它将一个看似复杂的、带有故事背景的实际问题抽象成一个纯粹的图论模型然后用成熟高效的算法一击即破。简单来说这道题描述了一个这样的场景在深海的某个区域有一个由网格点构成的“海底矿区”每个网格边即连接两个相邻点的路径上散布着不同价值的“标本”。我们拥有多支机器人小队每支小队有指定数量的机器人需要从不同的起点出发前往不同的终点。机器人在沿着网格边移动时可以采集该边上的标本并获得其价值。但这里有个关键限制每条边上的标本数量是有限的即一条边被一个机器人采集后其价值对于后续的机器人可能减少或消失。我们的目标是规划所有机器人的行进路线使得采集到的标本总价值最大。如果你熟悉网络流尤其是费用流此刻可能已经会心一笑了。这不就是一个典型的“多源多汇”、“边有容量和费用”的最大费用最大流问题吗没错这道题的经典之处就在于它完美地诠释了如何将一个带有“资源竞争”和“路径规划”元素的题目转化为网络流模型。通过这道题你不仅能学会费用流的应用更能掌握一种将具体问题抽象为流网络的核心思维。接下来我将带你彻底拆解这个模型从思路构建到代码实现最后分享一些我调试这类题目时积累的独家心得。2. 核心思路拆解如何将海底网格变成一张流网络面对任何网络流建模题第一步也是最关键的一步就是确定网络中的“流”到底代表什么。在这个问题里流很自然地代表了在海底移动的机器人。我们的目标是让尽可能多的机器人流从各自的起点源点移动到各自的终点汇点并在移动过程中经过那些带有价值的边产生费用同时遵守每条边上标本数量的限制边的容量。2.1 节点与边的设计模型构建的核心在于对原问题网格图的处理。通常题目给出的海底区域是一个P x Q的网格。一种直观的想法是把每个网格点当作网络中的节点。但这样会有一个问题标本是分布在边上的而不是在点上。因此我们需要通过“点拆边”或“边化点”的技巧来处理。最经典且高效的建模方法如下节点将每一个网格坐标(i, j)直接映射为一个唯一的节点编号。例如对于坐标(i, j)其节点编号可以是idx i * Q j假设行列从0开始。这样我们就有P * Q个节点。边代表移动与采集这是建模的精髓。对于原网格中的一条有向边比如从(i, j)到(i, j1)的向东边我们在流网络中建立两条有向边第一条边采集边容量为1费用为该边上的标本价值。这条边代表一个机器人第一次经过这条边并成功采集了标本获得了全部价值。因为标本被采集后就没了所以容量为1。第二条边通行边容量为无穷大或一个足够大的数如题目给出的机器人总数费用为0。这条边代表后续的机器人再经过这条边但已经无标本可采所以不产生价值。为什么是两条边这是为了区分“有收益的通行”和“无收益的通行”。网络流算法在寻找增广路时会优先选择费用高的边对于最大费用流。因此算法会尽量让流机器人走那些还有容量且费用高即还有标本的边。当那条边的容量用尽后流就只能走费用为0的边通行完美模拟了标本被采集一次后失效的设定。超级源点与超级汇点由于我们有多个起点机器人出发地和多个终点机器人目的地这是典型的多源多汇问题。标准网络流算法处理的是单源单汇。解决方法就是引入一个超级源点S和一个超级汇点T。从超级源点S向每个实际的起点(x, y)连一条边容量为该起点处机器人的数量k费用为0。这表示从这里提供了k个单位的“流”机器人。从每个实际的终点(x, y)向超级汇点T连一条边容量为该终点处需要接收的机器人数量k注意题目描述有时是到达即可有时是要求特定数量费用为0。这表示流到这里就被吸收了。2.2 最大费用最大流算法选择模型建好后我们需要一个算法来计算从S到T的流在满足容量限制的前提下使得总费用最大。这就是最大费用最大流问题。最常用的方法是SPFA或Bellman-Ford实现的连续最短路算法。为什么是SPFA而不是Dijkstra因为图中存在费用为负的边吗不在这个模型里所有边的费用标本价值都是非负的。但是当我们将其转化为最小费用最大流来求解时需要将边权取反。也就是说我们建立网络时边的费用w是标本的正价值但为了套用经典的最小费用流算法我们会将每条边的费用设置为-w。这样求最小费用流就等价于求原问题的最大费用流。而一旦引入负权边Dijkstra算法就无法直接使用了除非使用Johnson重标价或势能Dijkstra。对于竞赛编程使用SPFA来实现最小费用流是最简单、最不容易出错的尽管在最坏情况下复杂度较高但本题数据规模通常足以应付。算法流程简述以费用为边权此时已取反即-w在残留网络上不断寻找从S到T的最短增广路即单位花费最小的路径。找到后计算这条路径上能通过的最大流量flow即路径上所有边剩余容量的最小值。将flow单位的流推送到这条路径上并更新残留网络正向边容量减少flow反向边容量增加flow。累加总费用cost flow * dist[T]注意这里的dist[T]是取反后的最短路径长即-原收益所以累加的是负值。重复步骤1-4直到无法找到增广路为止。最终-cost就是我们想要的最大总收益。3. 代码实现与关键细节解析理论清晰后我们来看代码实现。我会以C为例并着重讲解几个容易出错的细节。3.1 数据结构定义首先定义边的结构体和网络流类。这里采用链式前向星存图方便处理反向边。#include bits/stdc.h using namespace std; const int MAXN 1000; // 根据题目网格最大尺寸调整P*Q 2 const int MAXM 10000; // 边数估计每个网格点最多4条边每条原边拆成2条网络边 const int INF 0x3f3f3f3f; struct Edge { int to, next, cap, cost; // 指向节点下一条边索引容量费用这里是取反后的费用 }; class MCMF { public: int head[MAXN], cnt; Edge edges[MAXM * 2]; // 注意要开两倍因为要存反向边 int dist[MAXN], pre[MAXN], incf[MAXN]; bool inq[MAXN]; MCMF() { memset(head, -1, sizeof(head)); cnt 0; } void addEdge(int u, int v, int cap, int cost) { // 加正向边 edges[cnt] {v, head[u], cap, cost}; head[u] cnt; // 加反向边 edges[cnt] {u, head[v], 0, -cost}; // 反向边初始容量为0费用为-cost head[v] cnt; } bool spfa(int s, int t) { memset(dist, 0x3f, sizeof(dist)); memset(inq, 0, sizeof(inq)); queueint q; q.push(s); dist[s] 0; inq[s] true; incf[s] INF; // 源点流量无限 while (!q.empty()) { int u q.front(); q.pop(); inq[u] false; for (int i head[u]; ~i; i edges[i].next) { int v edges[i].to, cap edges[i].cap, cost edges[i].cost; if (cap 0 dist[v] dist[u] cost) { dist[v] dist[u] cost; pre[v] i; // 记录前驱边 incf[v] min(incf[u], cap); if (!inq[v]) { q.push(v); inq[v] true; } } } } return dist[t] ! INF; // 汇点可达 } // 返回最大流和最小费用 pairint, int solve(int s, int t) { int maxflow 0, mincost 0; while (spfa(s, t)) { int flow incf[t]; maxflow flow; for (int u t; u ! s; u edges[pre[u] ^ 1].to) { int i pre[u]; edges[i].cap - flow; edges[i ^ 1].cap flow; // 利用异或1操作找到反向边 } mincost flow * dist[t]; } return {maxflow, mincost}; } };3.2 建图过程详解这是整个代码的核心必须严格对应之前的建模思路。int main() { int A, B; // A条纵向边向北B条横向边向东这里需要仔细看题通常是先列数再行数 int P, Q; // P行Q列 cin A B P Q; // 注意洛谷原题输入格式可能是先给A,B再给P,Q。且坐标描述可能从(0,0)或(1,1)开始。 // 我们统一将网格点(i,j)编号为 i*(Q1) j。因为P行Q列的网格有(P1)行点和(Q1)列点。 // 这里假设输入是P1行Q1列的点阵题目给出的是边的信息。 // 我们按(P1)*(Q1)个点来算。 int N (P1) * (Q1); // 总网格点数 int S N, T N 1; // 超级源点和汇点 MCMF mcmf; // 第一步读入横向边东向的标本价值 for (int i 0; i P; i) { for (int j 0; j Q; j) { // 横向有Q条边 int val; cin val; int u i * (Q1) j; int v u 1; // 向东移动列号1 // 添加两条边一条容量1费用为-val用于采集一条容量INF费用0用于通行 mcmf.addEdge(u, v, 1, -val); mcmf.addEdge(u, v, INF, 0); } } // 第二步读入纵向边北向的标本价值 for (int j 0; j Q; j) { for (int i 0; i P; i) { // 纵向有P条边 int val; cin val; int u i * (Q1) j; int v u (Q1); // 向北移动跳到下一行 mcmf.addEdge(u, v, 1, -val); mcmf.addEdge(u, v, INF, 0); } } // 第三步处理机器人的起点和终点 for (int i 0; i A; i) { int k, x, y; cin k x y; // k个机器人从(x,y)出发 int node_id x * (Q1) y; // 计算节点编号注意输入坐标可能从0或1开始需调整 mcmf.addEdge(S, node_id, k, 0); } for (int i 0; i B; i) { int k, x, y; cin k x y; // k个机器人需要到达(x,y) int node_id x * (Q1) y; mcmf.addEdge(node_id, T, k, 0); } auto [maxflow, mincost] mcmf.solve(S, T); cout -mincost endl; // 输出最大收益 return 0; }关键细节解析坐标转换与节点编号这是最容易出错的地方。题目输入的P和Q有时代表“网格数”有时代表“点数”。必须仔细阅读题目描述。通常“深海机器人问题”中P和Q表示海底区域的大小那么就有(P1) * (Q1)个网格点。节点编号公式id i * (Q1) j确保了每个点有唯一ID。务必自己画一个2x3的网格验证一下编号是否正确。边的方向题目通常规定机器人只能向东或向北移动从西南角到东北角。因此我们只建了从(i,j)到(i, j1)和到(i1, j)的边。如果你的图需要双向移动则需要对两个方向都建边。容量INF的设置通行边的容量理论上可以是任何大于等于最大可能流量的值。通常直接设为一个很大的数比如1e9或0x3f3f3f3f。在代码中我用了INF但要注意INF在费用流算法中通常用于距离初始化这里用作容量可能混淆。最好单独定义一个BIG常量。费用取反在addEdge时采集边的费用传入的是-val。这是为了后续调用最小费用流算法。最终答案需要再取反-mincost。4. 调试技巧与常见问题排查即便思路和代码都写出来了网络流题目依然可能因为一些隐蔽的错误导致WA错误答案或TLE超时。以下是我在刷题和比赛中总结的排查清单。4.1 常见WA原因建图错误占90%以上节点编号算错这是头号杀手。用一个小样例比如2x2网格打印出每个坐标(i,j)对应的节点编号id手动模拟一下边的连接看是否符合预期。边数开太小每条原边要拆成2条网络边每个机器人起终点要连2条边正向和反向。反向边也要算进去如果使用链式前向星MAXM至少要是预估边数的2倍。开小了会导致越界、数据覆盖产生各种灵异错误。容量或费用设错采集边的容量一定是1吗如果一条边上的标本可以被多个机器人采集容量就要相应增加。通行边的费用一定是0吗确认无误。超级源汇连接错误检查从S连向起点的边容量是否为机器人数量k从终点连向T的边容量是否为需要接收的数量k。方向别反了。算法实现细节SPFA判环与负环理论上由于我们加入了反向边费用为-cost在残留网络中可能存在负环。但标准的最小费用流算法连续最短路要求初始网络无负环且每次在最短增广路上增广不会引入新的负环。所以使用SPFA求最短路是安全的。但如果你的图本身建模有误造成了负环SPFA可能会死循环。可以增加计数器限制松弛次数。费用溢出总费用mincost可能很大需要使用long long。INF也要用0x3f3f3f3f3f3f3f3f。4.2 性能优化与TLE应对本题数据规模通常不会太大但如果你遇到TLE或者想写出更稳健的代码可以考虑以下几点使用势能DijkstraPrimal-Dual这是最小费用流的标准高效算法。它通过引入“势能”h[v]将原图所有边权变为非负从而可以使用更快的Dijkstra算法求最短路。虽然代码稍复杂但性能稳定尤其适合边权非负或经过处理后非负的图。对于本题所有原始边权标本价值非负取反后为负但可以通过初始势能比如用一次SPFA计算将其调整为非负。// 势能更新对于每条边(u,v)新的边权 w w h[u] - h[v] // 在每次Dijkstra后更新势能h[v] dist[v]实现Primal-Dual算法能有效避免SPFA的不稳定最坏情况。检查边数如果P和Q较大比如几百网格边数会达到O(P*Q)级别再乘以2双向采集/通行边数可能达到几十万。确保你的MAXM常量足够大。输入优化使用scanf或ios::sync_with_stdio(false)加速C的输入输出。4.3 个人调试心得从小样例开始不要一上来就跑题目的完整样例。自己构造一个最小的、能手动计算结果的例子。比如一个1x2的网格只有一条横向边上有价值为5的标本一个机器人从(0,0)到(0,1)。手动算最大收益是5。然后用你的程序跑看输出是不是5。如果不是用调试器或打印中间图结构如每个点的出边来查。可视化工具对于复杂的建图可以在调试时写一个简单的函数将S、T和所有节点、边的容量费用打印出来。虽然繁琐但一次成功的可视化调试能帮你彻底理解模型。理解“流”的路径在调试时可以尝试在spfa找到增广路后打印出这条路径上的节点。看看机器人实际是怎么走的是否符合你的预期。这能帮你发现建图方向错误等问题。关注“多组数据”洛谷的题目可能是多组测试数据虽然本题通常不是。如果你的代码跑多组数据一定要记得初始化MCMF类的head数组、cnt计数器必须在每组数据开始前清零。5. 模型扩展与思维提升“深海机器人问题”是网络流24题中非常经典的一道它代表了一类“资源竞争型路径规划”问题。掌握它你就掌握了一把钥匙。我们可以看看这个模型还能解决哪些变种问题多次采集问题如果一条边上的标本可以被采集多次比如最多k次那么只需要将“采集边”的容量从1改为k即可。通行边容量依然是INF。不同机器人价值不同如果不同种类的机器人采集同一标本获得的价值不同这就变成了一个“多商品流”问题建模会复杂很多可能需要对边进行进一步拆分或使用其他技巧。带有“时间”或“顺序”的采集如果标本价值会随时间衰减或者机器人有先后顺序这通常需要结合分层图时间拆点等技术。从最大费用流到最小费用流很多题目是求最小成本例如运输问题。其本质完全相同只是边费用代表成本我们直接求最小费用最大流即可无需取反。这道题的精髓在于“一条边拆成两条”来区分有收益的首次使用和无收益的后续使用。这种思想在诸如“软件安装依赖”、“任务调度”等问题中也有体现。当你遇到一个问题其中某些“资源”或“通道”在首次被占用时会产生效益或成本而重复占用则效益不同或成本变化时就应该立刻想到这个模型。最后网络流的学习离不开大量的练习和总结。每做一道题不仅要AC更要问自己这个问题的“流”是什么“容量”限制了什么“费用”又代表了什么源和汇是如何设置的只有把建模过程像解数学题一样清晰地写下来才能真正内化这种强大的抽象思维能力。这道“深海机器人问题”就是一个绝佳的起点它干净利落地展示了如何将生动的故事背景转化为严谨优美的图论模型并用算法高效求解。希望这篇详细的拆解能帮你打通任督二脉在网络流的学习道路上走得更稳更远。如果在实现过程中遇到其他坑点不妨回头再看看建图部分十有八九问题就出在那里。