UVa 11082 Matrix Decompressing

题目大意

给定一个 $R\times C$ 的正整数矩阵，已知它的 累积行和 与 累积列和 ，要求还原出原矩阵的所有 $R\times C$ 个元素。

具体来说：

• $RowSum(i)={\sum }_{j=1}^C{A}_{ij}$
• $CumulativeRowSum(i)={\sum }_{k=1}^{i}RowSum(k)$
• $ColumnSum(i)={\sum }_{j=1}^R{A}_{ji}$
• $CumulativeColumnSum(i)={\sum }_{k=1}^{i}ColumnSum(k)$

题目保证至少有一个解，并且规定矩阵中每个元素是 $1$ 到 $20$ 之间的整数。
若有多组解，输出任意一组即可。

输入格式

第一行是测试用例数 $T$ 。
每个测试用例包含三行：

输出格式

对每个测试用例，先输出一行 Matrix x，其中 $x$ 是测试用例编号（从 1 开始）。
接下来输出 $R$ 行，每行 $C$ 个整数表示矩阵元素。

解题思路

1. 转化为网络流模型

我们已知的是累积和，可以先将其转化为行和与列和：

设：
$$\begin{gathered} r_i=CumulativeRowSum(i)-CumulativeRowSum(i-1) \\ {c}_j=CumulativeColumnSum(j)-CumulativeColumnSum(j-1) \end{gathered}$$
其中 $CumulativeRowSum(0)=0$ ， $CumulativeColumnSum(0)=0$ 。

那么 $r_i$ 就是第 $i$ 行的和， $c_j$ 就是第 $j$ 列的和。

问题转化为：构造一个 $R\times C$ 的正整数矩阵，使得第 $i$ 行的和为 $r_i$ ，第 $j$ 列的和为 $c_j$ ，且每个元素在 $[1,20]$ 之间。

2. 建立流量网络

这是一个典型的 二分图匹配 问题，可以用 最大流 解决。

构造一个网络：

• 源点 $S$ 连接 $R$ 个行结点 $R_i$ ，容量为 $r_i$
• 列结点 $C_j$ 连接汇点 $T$ ，容量为 $c_j$
• 每个行结点 $R_i$ 连接每个列结点 $C_j$ ，容量为 $19$（因为元素最大是 $20$，最小是 $1$，所以流量范围是 $019$，实际值$=$流量$+1$）

这样，从 $S$ 到 $R_i$ 的流量表示第 $i$ 行的总分配量，从 $R_i$ 到 $C_j$ 的流量表示 $A_{ij}-1$ ，从 $C_j$ 到 $T$ 的流量表示第 $j$ 列的总分配量。

3. 流量与矩阵元素的关系

设 $f_{ij}$ 为边 $R_i\to C_j$ 的流量（ $0\le f_{ij}\le 19$ ），则：
$$A_{ij}=f_{ij}+1$$

因为 $f_{ij}\in [0,19]$ ，所以 $A_{ij}\in [1,20]$ ，满足题目要求。

4. 流量约束

行和约束：
$$\sum _{j=1}^C(f_{ij}+1)=r_i\Rightarrow \sum _{j=1}^C{f}_{ij}=r_i-C$$

列和约束：
$$\sum _{i=1}^R(f_{ij}+1)=c_j\Rightarrow \sum _{i=1}^R{f}_{ij}=c_j-R$$

这样我们就把原问题转化为一个 带下界（最小为 $0$）和上界（最大为 $19$）的流分配问题 ，可以用 $\text{Dinic}$ 算法 求解最大流。

算法步骤

时间复杂度

顶点数 $V=R+C+2\le 42$ ，边数 $E=O(R\times C)$ 。
$\text{Dinic}$ 算法在二分图上复杂度为 $O(\sqrt{V}E)$ ，完全可行。

参考代码

// Matrix Decompressing
// UVa ID: 11082
// Verdict: Accepted
// Submission Date: 2023-05-31
// UVa Run Time: 0.000s
//
// 版权所有（C）2023，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f; // 定义无穷大值

// 网络流中的边结构体
struct arc {
int u, v; // 边的起点和终点
int capacity; // 边的容量
int residual; // 边的剩余容量
int next; // 下一条边的索引（邻接表）
};

// Dinic 最大流算法类
class Dinic {
private:
arc *arcs; // 存储所有边的数组
int vertices; // 顶点总数
int source, sink; // 源点和汇点
int idx; // 当前边的索引
int *head; // 每个顶点的第一条边索引（邻接表头）
int *dist; // BFS 中的距离数组
int *current; // 当前弧优化数组

// BFS 分层：构建层次网络
bool bfs() {
memset(dist, –1, sizeof(int) * vertices); // 初始化所有距离为 -1
queue<int> q;
q.push(source);
dist[source] = 1; // 源点距离设为 1（或 0，这里设为 1 避免与 -1 混淆）

while (!q.empty()) {
int u = q.front(); q.pop();
if (u == sink) break; // 到达汇点

// 遍历 u 的所有出边
for (int i = head[u]; ~i; i = arcs[i].next)
if (arcs[i].residual > 0 && dist[arcs[i].v] < 0) {
// 如果还有剩余容量且目标顶点未访问
dist[arcs[i].v] = dist[u] + 1;
q.push(arcs[i].v);
}
}
return dist[sink] > 0; // 返回是否能到达汇点
}

// DFS 寻找增广路
int dfs(int u, int flow) {
if (u == sink) return flow; // 到达汇点，返回流量

// 当前弧优化：从上次检查到的边继续
for (int &i = current[u]; ~i; i = arcs[i].next) {
int v = arcs[i].v, r = arcs[i].residual;

// 确保按层次网络前进且还有剩余容量
if (dist[v] == (dist[u] + 1) && r > 0) {
int volume = dfs(v, min(r, flow)); // 递归寻找增广路
if (volume > 0) {
// 更新边的剩余容量
arcs[i].residual -= volume;
arcs[i ^ 1].residual += volume; // 反向边增加容量
return volume;
}
}
}
return 0; // 没有找到增广路
}

public:
// 构造函数：初始化图
Dinic(int v, int e, int s, int t) {
arcs = new arc[e]; // 分配边数组空间
vertices = v;
source = s, sink = t;
idx = 0;
head = new int[v];
dist = new int[v];
current = new int[v];
memset(head, –1, sizeof(int) * v); // 初始化邻接表头为 -1
}

// 析构函数：释放内存
~Dinic() {
delete [] arcs;
delete [] head;
delete [] dist;
delete [] current;
}

// 添加一条有向边及其反向边
void addArc(int u, int v, int capacity) {
// 正向边：u -> v
arcs[idx] = (arc){u, v, capacity, capacity, head[u]};
head[u] = idx++;

// 反向边：v -> u，初始容量为 0
arcs[idx] = (arc){v, u, capacity, 0, head[v]};
head[v] = idx++;
}

// 计算最大流并输出矩阵
int maxFlow(int r, int c) {
int flow = 0;

// Dinic 主循环
while (bfs()) { // 构建层次网络
// 当前弧优化：重置当前弧数组
for (int i = 0; i < vertices; i++)
current[i] = head[i];

// 多次 DFS 寻找增广路
while (int delta = dfs(source, INF))
flow += delta;
}

// 从残余网络中提取矩阵元素
int matrix[32][32] = {}; // 存储结果矩阵

// 遍历所有边，找到连接行结点和列结点的边
for (int i = 0; i < idx; i++) {
// 如果这条边是从行结点到列结点
if (1 <= arcs[i].u && arcs[i].u <= r &&
r + 1 <= arcs[i].v && arcs[i].v <= r + c) {
// 实际流量 = 原始容量 – 剩余容量
// 矩阵元素 = 流量 + 1（因为流量表示 A[i][j] – 1）
matrix[arcs[i].u – 1][arcs[i].v – 1 – r] =
arcs[i].capacity – arcs[i].residual + 1;
}
}

// 输出矩阵
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (j) cout << ' '; // 元素间用空格分隔
cout << matrix[i][j];
}
cout << '\\n';
}

return flow; // 返回最大流值（本题中不需要）
}
};

// 全局数组：存储累积行和与累积列和
int crs[32]; // Cumulative Row Sums
int ccs[32]; // Cumulative Column Sums

int main(int argc, char *argv[]) {
// 加速输入输出
cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);

int T; // 测试用例数
cin >> T;

for (int cs = 0; cs < T; cs++) {
int R, C; // 矩阵的行数和列数
cin >> R >> C;

// 网络流图的顶点：0=源点，1~R=行结点，R+1~R+C=列结点，R+C+1=汇点
int source = 0, sink = R + C + 1;

// 创建 Dinic 对象（顶点数50足够，边数10000足够）
Dinic dinic(50, 10000, source, sink);

// 读入累积行和
for (int i = 1; i <= R; i++)
cin >> crs[i];

// 读入累积列和
for (int i = 1; i <= C; i++)
cin >> ccs[i];

// 计算行和：r_i = 累积行和(i) – 累积行和(i-1)
for (int i = R; i >= 1; i—)
crs[i] -= crs[i – 1];

// 计算列和：c_j = 累积列和(j) – 累积列和(j-1)
for (int i = C; i >= 1; i—)
ccs[i] -= ccs[i – 1];

// 建图：添加主要边
// 源点到行结点：容量为行和
for (int i = 1; i <= R; i++)
dinic.addArc(source, i, crs[i]);

// 列结点到汇点：容量为列和
for (int i = 1; i <= C; i++)
dinic.addArc(R + i, sink, ccs[i]);

// 添加辅助边以确保流量可行（处理下界约束）
// 行结点到汇点：容量为 C（每行有 C 个元素，每个至少为 1）
for (int i = 1; i <= R; i++)
dinic.addArc(i, sink, C);

// 源点到列结点：容量为 R（每列有 R 个元素，每个至少为 1）
for (int i = 1; i <= C; i++)
dinic.addArc(source, R + i, R);

// 行结点到列结点：容量为 min(19, 行和-C)
// 19 是因为元素最大为 20，流量表示 A[i][j]-1，所以最大流量为 19
// 行和-C 是因为每行有 C 个元素，每个至少为 1，所以可用于分配的流量为 r_i – C
for (int i = 1; i <= R; i++)
for (int j = 1; j <= C; j++)
dinic.addArc(i, R + j, min(19, crs[i] – C));

// 输出格式：测试用例之间空一行（第一个除外）
if (cs)
cout << '\\n';

// 输出标题
cout << "Matrix " << cs + 1 << '\\n';

// 计算最大流并输出矩阵
dinic.maxFlow(R, C);
}

return 0;
}

代码关键点解释

1. 网络流建模技巧

代码中使用了多种技巧来确保流量的正确性：

• 反向边：每条正向边都有一条对应的反向边，用于实现流量的调整。
• 层次网络：$\text{BFS}$ 构建距离标号，确保 $\text{DFS}$ 按照最短路径增广。
• 当前弧优化：避免重复检查已经无法增广的边，提高效率。
• 辅助边：添加 $S->C_j$ 和 $R_i->T$ 边来处理元素的下界约束（每个元素至少为 $1$）。

2. 矩阵元素的提取

矩阵元素的计算公式为：

A[i][j] = 原始容量 – 剩余容量 + 1

这是因为：

• 原始容量：表示允许的最大流量（即 $A[i][j]-1$ 的最大值）
• 剩余容量：表示还未使用的流量
• 实际流量 = 原始容量 – 剩余容量：表示实际使用的流量（即 $A[i][j]-1$）
• +1：恢复为实际的矩阵元素值

3. 边界情况处理

• 当 $crs[i]-C$ 可能为负数时，$min(19,crs[i]-C)$ 确保容量非负。
• 题目保证至少有一个解，所以最大流一定能找到可行解。
• 矩阵大小限制在 $20\times 20$ 以内，因此数组大小 $32$ 足够使用。

总结

本题的关键在于：

这道题很好地展示了如何将矩阵构造问题转化为网络流问题，是练习 最大流建模 的经典题目。通过添加详细的中文注释，希望能帮助读者更好地理解网络流算法的实现细节和建模技巧。