UVA11082 Matrix Decompressing(矩阵解压) 最大流

末蓝、 2022-10-02 11:46 130阅读 0赞

## 题意：对于一个R行C列的正整数矩阵，(1<=R,C<=20),设a\[i\]为前i行所有元素之和，b\[i\]为前i列所有元素之和，已知道R，C，和数组a，b，找一个满足条件的矩阵，矩阵中的元素必须是1~20之间的正整数，输入保证有解。 ##

## 分析：刘汝佳提供的解题思路是这样的：因为知道前 i 行所有元素之和 a\[i \]以及前 j 列所有元素之和 b\[i\] ，那么就能计算出第 i 行所有元素之和以及第 j 列所有元素之和，如果矩阵中的每个数都减一，那么每一行之和都会减少C，每一列都会减少R，这样每个元素的范围变成了0~19，设每一行之和减一为 c\[i\] ，每一列之和减一为 d\[j\]。建立一个二分图，每行对应一个X节点，每一列对应一个Y节点，从原点到每一个X节点引一条弧（假设为第一类弧），容量为 c\[i\] ；从每一个Y节点到汇点引一条弧（假设为第二类弧），容量为 d\[j\] ；从每一个X节点到每一个Y节点引一条弧（第三类弧），容量为19,。跑一遍最大流，如果第一类弧和第二类弧都满载（流量等于容量），那么每个从X节点到Y节点弧的流量就是矩阵中的元素，否则不存在。 ##

## 为什么这样是正确的呢？首先注意到这一点：矩阵中的每个元素都减一。为什么要减一？这是为了求最大流的方便，题目要求矩阵中的元素要在1到20之间，而在求最大流的时候是有可能出现0流的，所以这样减去一之后求出的流量（矩阵中的元素）在0到19之间，输出时加一就可以了。那这样建图和求解的原理是什么？对于每一个X节点，都是只有一个入流，多个出流（分别流向每一个Y节点），显然多个出流的和正好等于入流；同理，对于每一个Y节点，有多个入流（分别来自每一个X节点），只有一个出流，显然多个入流的和等于出流。再考虑每一类弧的意义：第一类弧，以每一行所有元素之和为容量；第三类弧，以每一列所有元素之和为容量；第二类弧，最终流量为矩阵中的每一个元素。也就是说，第一类弧分成多个分支，每一个第一类弧都分出一个分支汇到同一个第三类弧。再考虑矩阵：把每一行的和分成多个元素，每一行的和都会分出一个元素排列在同一列，组成这一列的和。其中有很大的相似性，其实就是问题的变形，只要求出每一个第二类弧的流量，就是求出了矩阵中的每一个元素。建图如下。 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70][]

## 总结：第i行到第j列的最大流，就是（i,j）元素，行列问题经常可以转化为网络流问题。 ##

## 代码：待补。 ##

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70]: /images/20220112/6bebf85cee1a4565a5e69ae2eaf77984.png