UVa 11082矩阵还原：上下界转普通最大流建模全解析

第一次在 UVa 上看到 11082 Matrix Decompressing 这个题名时我的第一反应是这不就是个线性方程组还原矩阵吗高斯消元或者直接按行扫一遍不就出来了结果真正动手才发现这个题是典型的“表面数学、内核网络流”而且它考察的还不是那种一眼能看穿的裸流是带下界的容量建模。如果你也卡在这个题的“为什么这么建图”上或者你只是想找一道能把上下界网络流转成普通最大流的经典题吃透那这篇文章正好合适。这道题在 UVa 上的定位算是中档偏上的网络流建模题适合已经掌握 Dinic 或 ISAP 模板、但还想提升“如何把实际问题抽象成流模型”能力的人。它不考你的最大流模板背着多熟考的是你能不能把一个 1 到 20 的整数矩阵还原问题拆成“先减一、再跑最大流、最后加一”的三步曲。我会从题目理解开始逐步拆解为什么行和列的前缀和能变成流量约束并附带可以直接抄的 C 实现最后聊几个我真实踩过的坑。1. 题目到底在说什么读懂“Decompressing”这个动作1.1 输入的不是矩阵而是行和列的前缀和题目给了一个 R 行 C 列的矩阵但是不给你矩阵本身。给你两行数组第一行有 R 个整数是每一行的前缀和也就是rowPrefix[i] 前 i 行的元素总和。第二行有 C 个整数是每一列的前缀和也就是colPrefix[j] 前 j 列的元素总和。所以如果题目给了rowPrefix [3, 8]说明第一行总和是3 - 0 3第二行总和是8 - 3 5。列同理。很多第一次做这题的人会直接拿前缀和当行和用这是第一个隐藏陷阱后面我会专门展开说。题目要求你反推出任意一个满足条件的原始矩阵矩阵里的每个元素必须在 1 到 20 之间且行和、列和与给定数据吻合。R 和 C 都不超过 20所以矩阵最大规模是 20×20元素总数最多 400 个。1.2 为什么“任意一个”就意味着有多个解这题不要求唯一解只要输出任意一个合法矩阵就行。这一条很重要因为如果要求唯一解问题性质就变了可能需要解线性方程组甚至做整数规划。但题目只要求“一个可行解”这就给网络流留下了空间。因为网络流跑出来的是一个可行流任何一个可行流都能映射回一个合法矩阵而不需要关心是不是“标准答案”。你可能会想那我不如直接贪心填比如每行从左到右填先填大数再填小数实际上贪心很容易失败。因为行约束和列约束是耦合在一起的你在某一行填了一个数这一格所在列的和配额也被消耗了。你在这个局部觉得很优到下一行可能发现某一列剩下的配额已经不够至少填 1 了。1.3 元素必须落在 [1, 20] 是一个强约束注意元素范围不是 0 到 20而是 1 到 20。这有什么区别区别非常大。如果允许 0我们可以直接把每行总和拆成若干个“不超过 20 的非负整数”然后随便分配到各列只要每列不超过限制。这仍然有列约束但至少每个格子的下界是 0建模的时候所有容量都是正的舒服很多。有了下界 1每个格子天生就占了一份“基本额度”。这个下界 1 是整个题目的题眼。它决定了你不能单纯地把行和当作从源点流出的总流量因为你得保证每个行点到列点的边上至少要流 1 个单位而普通最大流模型不支持“至少流多少”这种容量下限。所以得想办法把下界 1 消掉而方法就是“整体减一”。2. 核心建模思路先减一把下界变成普通容量2.1 为什么不能直接建最大流模型先回顾一下最大流的经典结构有一个源点 S一个汇点 T中间一堆节点和边。每条边有一个容量上限 c实际流量 f 要满足 0 ≤ f ≤ c。也就是说普通最大流只支持“最多流多少”不支持“最少流多少”。如果我们把矩阵的每个元素 a_ij 看成从第 i 行节点流向第 j 列节点的流量那么这一格的流量下限是 1上限是 20。可普通网络流的边上只能写一个上限没办法写下限。这就是最直接的冲突。但如果我们把每个元素都减去 1情况就变了。设 b_ij a_ij - 1则 b_ij 的取值范围是 0 到 19下界变成了 0上界变成了 19。这时候 b_ij 就能直接作为一条边上允许的流量因为它的下界是 0符合普通最大流的要求。这个“整体减一”的操作其实就是在把带下界的网络流模型转换成普通网络流模型。等流跑完之后再把每个 b_ij 加 1 还原成 a_ij 就行。2.2 行和和列和也要跟着减一既然每个元素都减了 1那每一行、每一列的总和也要相应变化。原矩阵中第 i 行的行和记为 rowSum[i]因为这一行一共有 C 个元素每个元素都减了 1所以在新矩阵 b 中第 i 行的行和应该是rowSum[i] rowSum[i] - C同理第 j 列的列和变为colSum[j] colSum[j] - R这个“行和减列数、列和减行数”很容易写反。我一开始就搞反过写成行和减 R 了结果怎么跑怎么不对。你只要记住每个元素减 1一行有 C 个元素所以整行少了 C不是少了 R。列同理一列有 R 个元素所以整列少了 R。这里还可以从总量上验证一下。原矩阵所有元素总和等于sum(rowSum)也等于sum(colSum)。减一之后所有元素总和应该等于total_b sum(rowSum) - R * C用列和来算也一样total_b sum(colSum) - R * C这两个值必须相等。如果不等说明输入数据本身有问题但这题保证输入合法所以不需要额外判断。不过写程序时可以顺手算一下做个 sanity check具体怎么断点验证我在第 4 节会说。2.3 建图源点、行节点、列节点、汇点减一之后我们可以把问题转成标准最大流。图的结构非常对称从源点 S 连接到每个行节点 i容量为rowSum[i] - C。这表示第 i 行在减一之后总共还能分配出去的“剩余和”。从每个行节点 i 连接到每个列节点 j容量为 19。这表示 b_ij 最大是 19最小是 0应用普通边容量 0~19 即可。从每个列节点 j 连接到汇点 T容量为colSum[j] - R。这表示第 j 列在减一之后总共能接收的“剩余和”。建好这个图之后跑一次从 S 到 T 的最大流。如果最后最大流的值等于total_b说明我们找到了一个可行流。那么原矩阵的元素就是a_ij (行节点 i 到列节点 j 这条边上的流量) 1因为这条边上的流量就是 b_ij加 1 正好还原出 a_ij。2.4 为什么最大流一定等于 total_b可行性论证你可能要问最大流跑出来的值能不能保证恰好等于 total_b会不会跑出一个小于 total_b 的流关键点在于题目保证输入一定来自某个合法矩阵所以原矩阵必然存在。我们把这个合法矩阵每个元素减一就得到一组满足上面所有容量约束的 b_ij。这一组 b_ij 天然就是图上的一个可行流它的流量值就是 total_b。因此这张图的最大流至少是 total_b。另一方面源点 S 连出去的所有边的容量总和恰好是sum(rowSum[i] - C) sum(rowSum) - R*C total_b所以从 S 出发的总流量不可能超过 total_b。最大流也不可能超过 total_b。两边一夹最大流必然恰好等于 total_b。这个论证非常重要它保证了“跑最大流”这个动作一定能把所有边的流量“灌满”到目标值不会出现最大流跑完却发现流量不足的情况。同时也说明如果输入保证有解那我们根本不需要写额外的可行流判断逻辑。只要最大流算法实现正确流到最大时每条行到列的边上自然分配好了一组合法的 b_ij。这也是这类“给定容量约束求可行解”题目最常见的设计逻辑把可行解的存在性直接建立在输入合法性上然后依靠最大流把可行解重新构造出来。3. 实操完整代码与关键细节3.1 节点编号与建边顺序我直接用 Dinic 实现因为最大流规模很小R 和 C 最多 20节点数最多 42边数最多也就 400 多条其实 EK 也能过。但 Dinic 写起来更通用后面做其他题也能复用。节点编号如下源点0行节点1 到 R列节点R1 到 RC汇点RC1建边时注意同时加反向边容量为 0。这是最大流算法的基本要求忘记加反向边是新手最常犯的错。代码里我习惯把addEdge(u, v, cap)写成同时插入正向边和反向边的形式并将反向边的索引记录下来方便最后读取流量。3.2 Dinic 模板下面是我常用的 Dinic 实现带当前弧优化。这个模板在节点数几百、边数几千的范围内表现都很稳定应付这道题绰绰有余。#include bits/stdc.h using namespace std; struct Edge { int to, cap, rev; }; class Dinic { public: vectorvectorEdge G; vectorint level, iter; int n; Dinic(int n) : n(n) { G.resize(n); } void addEdge(int u, int v, int cap) { G[u].push_back({v, cap, (int)G[v].size()}); G[v].push_back({u, 0, (int)G[u].size() - 1}); } void bfs(int s) { level.assign(n, -1); queueint q; level[s] 0; q.push(s); while (!q.empty()) { int u q.front(); q.pop(); for (auto e : G[u]) { if (e.cap 0 level[e.to] 0) { level[e.to] level[u] 1; q.push(e.to); } } } } 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] 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 maxFlow(int s, int t) { int ans 0; while (true) { bfs(s); if (level[t] 0) break; iter.assign(n, 0); int f; while ((f dfs(s, t, INT_MAX)) 0) { ans f; } } return ans; } };这个模板里rev记录的是反向边在对面节点邻接表中的下标。当你访问一条正向边e时它的反向边就是G[e.to][e.rev]。这种写法比用 pair 存 to 和 cap 再额外存 revIdx 更直观。3.3 完整解题代码接下来是完整的main函数流程。这里我特意只写了核心逻辑输出部分配合printf控制格式。int main() { int T; scanf(%d, T); for (int kase 1; kase T; kase) { int R, C; scanf(%d%d, R, C); vectorint rowPrefix(R), colPrefix(C); for (int i 0; i R; i) scanf(%d, rowPrefix[i]); for (int j 0; j C; j) scanf(%d, colPrefix[j]); vectorint rowSum(R), colSum(C); rowSum[0] rowPrefix[0]; for (int i 1; i R; i) rowSum[i] rowPrefix[i] - rowPrefix[i-1]; colSum[0] colPrefix[0]; for (int j 1; j C; j) colSum[j] colPrefix[j] - colPrefix[j-1]; int S 0; int TNode R C 1; Dinic dinic(TNode 1); for (int i 0; i R; i) { dinic.addEdge(S, i 1, rowSum[i] - C); } for (int j 0; j C; j) { dinic.addEdge(R 1 j, TNode, colSum[j] - R); } for (int i 0; i R; i) { for (int j 0; j C; j) { dinic.addEdge(i 1, R 1 j, 19); } } int maxflow dinic.maxFlow(S, TNode); printf(Matrix %d\n, kase); for (int i 0; i R; i) { for (int j 0; j C; j) { if (j) printf( ); int val 0; for (auto e : dinic.G[i 1]) { if (e.to R 1 j) { val 19 - e.cap 1; break; } } printf(%d, val); } printf(\n); } if (kase ! T) printf(\n); } return 0; }这里读取矩阵元素的方式稍微绕了一下我遍历行节点 i1 的所有邻接边找到to是列节点 j 的那条正向边它的初始容量是 19当前的剩余容量是19 - 实际流量所以实际流量是19 - e.cap。再加 1 就还原成原矩阵元素。有些人的 Dinic 模板里Edge结构体没有保存flow字段而是直接通过容量变化推流量这种“初始容量减当前容量”的方法在这种固定容量下是可靠的。如果你更喜欢一开始就存个initCap边属性当然也可以代码会更直白一些。不过上面的写法省内存也避免了多加字段。3.4 一个 2×2 的手算验证纸上谈兵没有用我们拿一个最简例子走一遍流程。假设 R2C2。给定的前缀和为rowPrefix [4, 10] 表示第一行和为4第二行和为6 colPrefix [5, 10] 表示第一列和为5第二列和为5减一后的行和rowSum[0] 4 - 2 2 rowSum[1] 6 - 2 4减一后的列和colSum[0] 5 - 2 3 colSum[1] 5 - 2 3total_b 2 4 6同时 3 3 6没问题。建图后需要找到一个 2×2 的非负矩阵 b使得行和是 [2, 4]、列和是 [3, 3]且每个元素 ≤ 19。显然b [2 0 1 3]是一个可行解。那么原矩阵就是a [3 1 2 4]验证一下第一行和 314第二行和 246第一列和 325第二列和 145。完全吻合。你可以用这个例子调试代码确认最大流跑出来的值和手算一致。4. 进阶思考这类题目怎么一眼看出来是网络流4.1 识别“分配型”问题的共同特征很多同学的问题是看完题根本想不到网络流。这需要经验积累但也有规律可循。如果你的题目里出现“把某些总量分配到若干位置每个位置有上下限且行/列/组之间有交叉约束”那十有八九是网络流建模。因为网络流本质上就是一套处理“带容量限制的分配问题”的通用框架。拿这题来说矩阵的每个格子同时属于某一行和某一列所以行约束和列约束是交叉的。交叉约束正是网络流擅长处理的场景左边一排节点代表行右边一排节点代表列行节点和列节点两两连边就把“每个格子属于一行一列”这个关系给表达清楚了。如果再回顾一下经典的“二分图匹配”“分配问题”“运输问题”你会发现它们都是这种左行右列建图法的变体。4.2 上下界流量的处理套路这题最值得掌握的技巧是“整体减一”把下界 1 变成下界 0。如果以后遇到类似问题元素下限是 L上限是 R就可以先让所有值减去 L然后行和减 CL、列和减 RL行到列的容量设为 R-L。这样就能把一个带上下界的可行流问题转成普通最大流。这其实比再背一套“有上下界网络流算法”要轻量得多。只有当减完下界之后仍然存在某些边有非零下界、或者问题要求的不是可行流而是最小流/最大流时才需要引入真正的上下界网络流算法。但在竞赛和面试里绝大多数“带下界”的题目都能用这种“先减下界”的巧劲解决所以这套思维很值得沉淀下来。另外还有一些题目会反过来给你一个矩阵和部分行/列约束要求判断是否有解。这类题也可以用同样的建图跑最大流后看是否满流。满流是有解的充要条件不满流就是无解。这题的输入保证有解所以省了这一层判断但你把代码里的maxflow和total_b比较一下也能顺便实现这个功能。4.3 反向边在输出矩阵时的角色这里再提醒一个容易踩的坑如果你用 Dinic 跑完后想读取每条边上的流量千万别把反向边也算进去。反向边上的 cap 表示的是已经退回去的流量而不是真实流量。正确做法是读正向边的cap变化量。我在代码里通过判断e.to R 1 j来定位正向边同时还得保证读的是第一次加进去的那条正向边而不是反向边。怎么区分正向边和反向边在建图的时候正向边和反向边的to指向不同行节点 i 到列节点 j 的正向边to是R1j而反向边是列节点 j 指向行节点 i所以反向边的to是i1。如果你遍历的是行节点的邻接表那么所有to等于某个列节点编号的边就是正向边不会把反向边混进来。这是个小细节但有时候会干扰你定位流量。5. 常见问题与调试实录5.1 行前缀和、列前缀和算成行和列和时出错这是最经典的问题。有人直接把rowPrefix[i]当作第 i 行的行和来建图结果后面全错。记住题目给的是前缀和不是行和。求行和需要做差分rowSum[0] rowPrefix[0] rowSum[i] rowPrefix[i] - rowPrefix[i-1] (i 1)列同理。这个差分一定要在减一之前做顺序别反。如果先把前缀和减一再去差分数值会乱套。5.2 最大流跑了但结果不是整数矩阵网络流的一个重要性质是如果所有容量都是整数那么最大流一定有一个整数最优解。Dinic 的增广过程也是基于整数容量逐单位增广的所以最终跑出来的流量分配全是整数。你不会遇到小数流量这是普通最大流算法天然保证的。如果跑出来出现非整数流那一定是模板里用了浮点数容量本题不需要。5.3 矩阵元素可能大于 20 或者小于 1 吗理论上不会。因为行到列的边容量设成了 19流经每条边的流量 b_ij 最多是 19加 1 之后最多是 20。同时每条边流量最小是 0最大流算法里不会产生负流量加 1 之后最小是 1。所以输出一定在 [1, 20] 范围内。如果出现越界几乎可以断定是建图容量算错了。5.4 多组数据输出格式的坑UVa 这类题目对空行格式经常有特殊要求本题要求每个 Case 之间有一个空行。我的代码里用了if (kase ! T) printf(\n);保证最后一个 Case 后面不输出多余空行。有些 OJ 对行尾空格不敏感有些很敏感所以矩阵行末不要多打空格。我代码里在每行元素之间加空格行末printf(\n)结束不会多余。6. 从这道题延伸出去还能怎么变形6.1 行和列的限制换成区间假设题目改成每个格子元素在 [l_ij, r_ij] 之间不同格子上下界不一样那就不能简单地整体减一了。这时候需要把每个格子的下界 l_ij 单独拿出来先强制给每个格子分配 l_ij然后对应地修改行和列和的剩余配额最后再对剩余部分跑最大流。这个进阶方向值得思考一下理解了“[下界强制预留 上界做容量”的思路很多题都能套。6.2 求字典序最小的矩阵如果题目要求输出字典序最小或按某种优先级输出的矩阵单纯的最大流就不够了可能需要结合贪心或者费用流来做。比如你可以按字典序顺序逐个固定 b_ij 的值每次固定后重新跑最大流检查剩余部分是否可行。这个做法的核心还是“可行流判定”本质上仍然是网络流。6.3 二分图最大流的影子其实你看这个图的结构源点连行节点、行节点连列节点、列节点连汇点这个三层结构和二分图最大匹配的建图几乎一样。不过这里行节点到列节点的边不是单位容量而是一个范围容量。如果你把每个格子容量改成 1这就是一个匹配问题。理解了这道题对理解二分图匹配、带权匹配都有帮助因为它们用的都是同一套“左侧节点代表一类约束、右侧节点代表另一类约束”的框架。我个人在实际操作中的体会是这类建模题的难点从来不在模板而在你能不能冷静地把“每个格子元素有上下界”这句话翻译成容量。翻译完之后剩下的工作其实就是机械地建边和调格式。如果你第一次没做出来不用太沮丧网络流建模本来就需要大量题目积累。建议你拿这道题当模板题把它和另外几道经典建模题比如最大流求最小割、二分图匹配、上下界可行流放在一起对比总结时间久了看到这类题的题干脑子里就会自动浮现“左集合、右集合、源汇、容量”这几个关键词了。