第一次在 UVa 题库里看到 “Matrix Decompressing” 这个标题时我以为是矩阵分解、压缩那类大动干戈的题目。点进去读完题才明白这道题说的是另一件事已知一个 R 行 C 列矩阵的每一行之和、每一列之和并且矩阵里的每个元素都在 1 到 20 之间要求还原出任意一个满足条件的矩阵。这道题在 ACM 圈子里几乎被当成“网络流建模入门必刷题”所以收藏夹里躺了很久的人不止我一个。今天把完整思路、建图原理、代码和调试过程中踩过的坑一并整理出来。适合已经会写 Dinic 最大流、但对“怎么把一个矩阵题抽象成网络流”还比较困惑的选手也适合刚学完网络流、想找一道经典题练建模的新手。1. 先看懂题目这题不是让你填数是让你匹配约束1.1 题目到底给了什么、要什么输入是多组测试数据。每一组首先给出 R 和 C然后给出 R 个整数表示第 1 行到第 R 行的行和接着给出 C 个整数表示第 1 列到第 C 列的列和。要求你输出任意一个 R×C 矩阵满足矩阵中每个元素在 [1, 20] 区间内第 i 行所有元素之和等于输入的第 i 个行和第 j 列所有元素之和等于输入的第 j 个列和。题目保证输入数据一定存在至少一个可行矩阵。很多人的第一反应是这不就是解一个线性方程组吗确实如果把每个格子都当成未知数那么行和、列和加在一起一共是 R C 个等式未知数却有 R×C 个。方程个数远少于未知量个数所以解的空间其实很大。但问题没有那么简单因为每个格子不是任意实数它被死死地限制在 [1, 20] 这个整数区间里。这种“两边都有约束、中间变量互相牵连”的结构恰恰是网络流最擅长的领域。1.2 为什么贪心和暴力都行不通有人可能会想一行一行填过去先保证行和满足再微调列和行不行实测下来基本都会卡死。原因是每填一个格子会同时影响它所在行的总和和所在列的总和这是两个独立的约束。你为了满足某一列的和可能不得不去修改一个已经填好的格子这一改又把之前满足的行破坏了。来回调整的复杂度是指数级的靠递归回溯去搜矩阵在 R、C 都到 20 的情况下肯定跑不完。暴力的思路更不用提每个格子 20 种取值R×C 400 个格子搜索空间是 20^400这个数字大到你根本没法想象。所以这题的正确姿势就是把它当做一个“可行流判定 构造”的问题。而想通这一点之前必须先跨过一个最重要的坎每个元素有下界 1。2. 最关键的思路跃迁把范围 [1,20] 变成 [0,19]2.1 “至少是 1”才是建模真正的障碍如果矩阵元素范围是 [0, 20]那么建图会非常自然源点流向每一行容量是行和每一行流向每一列容量是 20每一列流向汇点容量是列和。流到格子上的流量就是矩阵元素的值。但题目规定元素至少是 1。这下麻烦就来了流量可以是 0可矩阵元素不允许是 0。直接建图的话你会找出一堆值为 0 的格子输出之后直接 WA。处理带下界的变量最常见的套路就是“平移值域”。既然最小值是 1那就先假设每个格子已经是 1 了剩下的问题只是在这个基础上再分配 0 到 19 的增量。2.2 整体减 1 后行列约束如何跟着变设原矩阵元素为 x(i, j)令 y(i, j) x(i, j) - 1。那么 y(i, j) 的取值范围是 [0, 19]。一行有 C 个元素每个都减 1一行的和总共会减少 C。所以新的行和满足r(i) r(i) - C一列有 R 个元素每个都减 1一列的和总共会减少 R。所以新的列和满足c(j) c(j) - R举个例子。R 2C 3输入行和是 8 和 10列和是 5、7、6。减完之后新行和8 - 3 510 - 3 7新列和5 - 2 37 - 2 56 - 2 4。所以现在的目标变成构造一个矩阵 y每个元素在 [0, 19] 内行和是 5、7列和是 3、5、4。这个矩阵没有下界约束了只有上界 19直接套网络流就顺了。注意必须同时检查总行和与总列和是否相等。题目保证有解所以这里自然是相等的但是在你写代码时自己构造数据验证时要注意这一点。3. 建图拆解源点、行节点、列节点、汇点四层结构3.1 四层节点的含义整个网络一共 R C 2 个节点一个超级源点 SR 个行节点编号可以取 1 到 RC 个列节点编号可以取 R 1 到 R C一个超级汇点 T。边的方向是固定的S 到行节点行节点到列节点列节点到 T。这个结构本质上是一张二分图套在最大流上。源点代表“总供给”汇点代表“总需求”中间的行节点负责按行分配列节点负责按列回收。如果你做过二分图匹配的题会觉得这个四层结构非常眼熟。区别在于二分图匹配里每条边的容量是 1而这里的容量是一个范围约束。3.2 三种边的容量为什么必须是这样三种边的容量设置如下边的类型容量含义S → 第 i 个行节点r(i)第 i 行最多能分配出去的增量总和第 i 个行节点 → 第 j 个列节点19每个格子 y(i, j) 不能超过 19第 j 个列节点 → Tc(j)第 j 列必须接收的增量总和为什么行节点到列节点的容量是 19 而不是 20因为我们已经把每个元素减了 1y(i, j) 的最大值是 19最后的答案会在读流量时再把那 1 加回去。如果这里写成 20那么还原出的矩阵元素可能达到 21直接超出题目给定的范围。为什么 S 到行节点容量是 r(i)而不是 r(i)因为 r(i) 是原矩阵第 i 行的和减掉 C 之后才是需要在这张网络上流动的增量总和。同理列节点到 T 的容量是 c(j)。3.3 流量守恒如何保证行列和一起满足最大流跑完之后对于任意一个行节点 iS → i 这条边的流量就是第 i 行分出去的总增量。当最大流等于全部新行和之和时这条边一定是满流所以第 i 行分出去的量恰好是 r(i)。再来看列节点 j。所有行节点流向它的流量加在一起就是它需要接收的总量。由于总流入等于总流出且最终最大流等于所有新列和之和j → T 也是满流状态所以列 j 收到的增量总和恰好是 c(j)。每一个边 (i, j) 上的流量就是 y(i, j)它天然在 [0, 19] 之间。因为最大流要求每条边都不能超过容量而边的容量正是 19。这里可以打一个比方把增量想象成水。源点是水库行节点是分水闸列节点是接水槽汇点是排水口。从分水闸到接水槽的每一根管道粗细一样都是 19表示每个格子最多接 19 个单位的水。最后只要总送水量等于总需求所有水槽都能正好接满。而每个分水闸向每个接水槽送了多少水就对应矩阵里那个位置的数值。4. 跑完最大流之后怎么把流量“翻译”成矩阵4.1 正向边、反向边与“读流量”的正确姿势用 Dinic 跑完最大流后网络里的边已经不是初始状态了。正向边的剩余容量被扣掉了反向边的容量增加了。如果你不熟悉这个机制直接从邻接表里随便拿一条边来读流量很容易把反向边当正向边读结果全错。我在实现时习惯在结构体里同时记录“这条边初始容量”。Dinic 在跑的过程里会修改边的 cap 字段把它一点一点扣小。那么对于一条正向边来说实际流过的流量就等于flow initCap - cap这个做法比维护一个独立的 flow 字段更简单也不会在 DFS 递归时搞混。为了精确拿到行 i 到列 j 那条边上的流量可以在建图时用一个二维数组 edgeIndex[i][j] 记录该正向边在行节点 i 的邻接表中的下标。最后还原矩阵时直接访问即可。遍历整个邻接表再判断终点是不是 j虽然也能做但稍不留神就会把反向边也算进去不如一开始就把下标记下来。4.2 为什么结果是整数如何自查输出网络流算法在整数容量下跑出来的最大流一定是整数值因为 Dinic 的增广过程只会传递整数流量。所以每条边上的流量也都是整数y(i, j) 天然是一个整数再加上 1 得到 x(i, j)也一定是整数。这个性质很重要。你不需要再对浮点数做任何取整处理直接 printf 或 cout 输出即可。还建议在代码里写一个 verify 函数输出矩阵之前先自己算一遍行和与列和跟输入对比。如果数据规模小这几乎不耗时间却能帮你迅速定位是建图错了还是读流量错了。很多 AC 代码其实都少做这一步结果在本地反复调不出错一交就 WA。5. 可提交的 C 代码Dinic 板子与完整流程5.1 核心数据结构与 Dinic 实现下面这份代码使用的也是“剩余容量”版本add_edge 时把反向边的 cap 设为 0跑最大流时扣正向边 cap增加反向边 cap。#include bits/stdc.h using namespace std; const int MAXN 55; const int INF 0x3f3f3f3f; struct Edge { int to, rev; int cap; }; vectorEdge G[MAXN]; int level[MAXN], iter[MAXN]; int edgeIndex[25][25]; // 行 i - 列 j 的正向边在 G[i] 中的下标 void add_edge(int u, int v, int cap) { G[u].push_back({v, (int)G[v].size(), cap}); G[v].push_back({u, (int)G[u].size() - 1, 0}); } bool bfs(int s, int t) { memset(level, -1, sizeof(level)); queueint q; level[s] 0; q.push(s); while (!q.empty()) { int u q.front(); q.pop(); for (int i 0; i (int)G[u].size(); i) { Edge e G[u][i]; if (e.cap 0 level[e.to] 0) { level[e.to] level[u] 1; q.push(e.to); } } } return level[t] 0; } int dfs(int u, int t, int f) { if (u t) return f; for (int i iter[u]; i (int)G[u].size(); i) { Edge e G[u][i]; if (e.cap 0 level[u] 1 level[e.to]) { int d dfs(e.to, t, min(f, e.cap)); if (d 0) { e.cap - d; G[e.to][e.rev].cap d; return d; } } } return 0; } int max_flow(int s, int t) { int flow 0; while (bfs(s, t)) { memset(iter, 0, sizeof(iter)); while (true) { int f dfs(s, t, INF); if (f 0) break; flow f; } } return flow; } int main() { ios::sync_with_stdio(false); cin.tie(0); int T; cin T; for (int kase 1; kase T; kase) { for (int i 0; i MAXN; i) G[i].clear(); memset(edgeIndex, -1, sizeof(edgeIndex)); int R, C; cin R C; vectorint row(R 1), col(C 1); for (int i 1; i R; i) cin row[i]; for (int j 1; j C; j) cin col[j]; int S 0; int Tnode R C 1; for (int i 1; i R; i) { int need row[i] - C; add_edge(S, i, need); } for (int i 1; i R; i) { for (int j 1; j C; j) { int before (int)G[i].size(); add_edge(i, R j, 19); edgeIndex[i][j] before; } } for (int j 1; j C; j) { int need col[j] - R; add_edge(R j, Tnode, need); } int flow max_flow(S, Tnode); cout Matrix kase \n; for (int i 1; i R; i) { for (int j 1; j C; j) { int idx edgeIndex[i][j]; int initCap 19; int residual G[i][idx].cap; int y initCap - residual; int x y 1; cout x; if (j C) cout ; } cout \n; } if (kase T) cout \n; } return 0; }5.2 建图、跑流、还原矩阵的三段式主流程主流程总共分四步读入 R、C、行和、列和建图S → 行节点容量为 row[i] - C行 → 列容量为 19列 → T 容量为 col[j] - R跑最大流遍历行节点到列节点的正向边取出剩余容量用 19 - residual 得到 y再加 1 输出。如果你不确定初始容量是不是 19直接在建边时把 19 保存到一个常量里或者用一个 initCap 数组记录避免写死在读流量阶段还能防止手滑改错。这一步的代码量不大但每一步都可能出问题。下面专门把我实际调试中踩过的坑列一下。6. 我调试这道题时踩过的坑以及排查思路6.1 清空与 multi-case最隐蔽的坑UVA 11082 是多组测试数据每一组案例的图必须完全重建。这里最容易犯的错是G[i].clear()之后忘记重新初始化edgeIndex或者上一个案例的节点编号残留导致第二组数据一上来就连错边。Dinic 板子里level和iter数组每次bfs和dfs前都会重新赋值所以这两个不太容易出问题。真正容易出问题的反而是边缘的edgeIndex数组。我第一版代码就是漏了memset(edgeIndex, -1, sizeof(edgeIndex))第一组数据运气好过了第二组直接越界访问跑出一堆负数。我的排查链路是先看 flow 是否等于所有新行和之和如果相等但答案仍错多半是读流量的边下标不对再打印边上算出的 y 值发现某几个格子是负数就知道是数组残留。6.2 容量设错、流量读反这类错误怎么定位第二个高发坑是行 → 列边容量写成 20。逻辑上看起来只差 1但矩阵元素上界会变成 21样例未必能测出来。所以要牢记建图时的容量对应的是减 1 后的增量范围而不是原矩阵元素的直接范围。还有读流量时反向边的问题。如果你在edgeIndex里记录的下标是正向边那么访问G[i][idx].cap拿到的剩余容量是扣减后的值初始值 19 减去它就是流量。如果你拿着反向边来读剩余容量可能是正数算出来的 y 会是负数或完全错误的数字。遇到这种情况我一般的做法是在建边时专门加一行注释// G[i].size() 就是当前正向边在 G[i] 中的下标 int before (int)G[i].size(); add_edge(i, R j, 19); edgeIndex[i][j] before;这样即使代码写乱了后面核查时也一眼能看出来。6.3 输出格式UVA 裁判从不通融这道题的输出格式要求每组输出一个Matrix X然后输出 R 行矩阵每一行的数字用空格隔开两组答案之间有一个空行。我对 UVA 的格式要求一向很小心因为它对行末空格和多余空行的处理在不同题目里不一样。稳妥起见我在每行输出之间手动控制空格最后一列之后不额外输出空格。多案例之间的空行用if (kase T) cout \n;来处理这样可以保证最后一组后面没有多余空行。如果你交上去是 Presentation Error基本就是格式问题。把样例输出的空白字符逐字节比对一下通常马上就能看出来。6.4 样例过了却 WA用对拍器找反例碰到样例能过、交上去 WA 的情况最有效的方式是写一个数据生成器 暴力验证程序。生成随机 R、C随机生成一个合法矩阵算出行和、列和作为输入然后跑你写好的网络流程序再检查结果是否满足行和、列和以及元素范围。这个方法看似麻烦却比肉眼盯代码高效得多。尤其是对这道题暴力验证只需要算一遍二维数组的和简单但有效。一旦反例数据能稳定复现错误就很好定位了。7. 从 UVa 11082 到一类题行列约束的通用建模手法7.1 把“下界”单拎出来的通用流程这题带给我最大的收获是学会了一种处理带下界变量的思路先看变量的取值范围如果最小值不是 0就整体减去最小值把范围变成从 0 开始相应的约束条件也要跟着调整之后在建图时边的容量就对应“减去下界后的上界”最后还原答案时把下界加回去。这个方法不止适用于矩阵题很多要求变量在某个区间内的网络流模型都可以这样处理。7.2 还能扩展到哪些更复杂的约束如果把每个格子元素的上界从 19 改成其他数字比如题目要求每个元素在 [1, 5] 之间那么减去 1 后行到列的容量就应该是 4计算方式完全一样。如果题目给的约束不是单纯的格子取值范围而是某些格子必须等于固定值或者某些格子不能超过某个值那么在建图时可以对那几条边单独设置容量甚至可以拆成多个节点来处理。这些变化都建立在同一个核心思想上网络流的边上流量代表一个变量边的容量代表这个变量的取值范围行和列约束通过源点到行节点、列节点到汇点来传递。掌握了这套归约方式之后很多“看起来完全不像网络流”的行列构造题其实都是同一张图的变体。最后再说一个习惯我后来做这类题会先花两分钟把变量的下界、上界、行约束和列约束分别写出来然后再决定要不要建图。只要这四个信息清晰图基本不会建错。UVa 11082 那个“减 1”的操作正是把下界从模型里剥离出来的最典型示范。