OIer博客

题目大意：一个n*n的矩阵A，每一行每一列的和都是偶数，需要分解成两个n*n矩阵B和C，要求A=B+C，且B和C每一行的和、每一列的和都相当。

解题思路

不难想到，偶数直接分一半，奇数尽量分一半，如果这个位置分多了（向上取整），记下来，下一次对应行、列分少一点（向下取整）。

按照这种思路，从上往下依次确定每个位置的大小，有可能出问题，如：

1 0 1

0 1 1

1 1 0

遇到不确定填+（向上取整），多了的填-（向下取整）：

+ 0 –

0 + –

此时已经无法再填，需要撤销操作（后悔：联想到二分图、网络流），复杂度就会增高。

因此，我们只能换一种填法：第一个不妨填+，然后在同一行找一个不确定的奇数填-，接着在该列找一个不确定的奇数填+……如此往复，必有一条欧拉回路，因为题目保证每一行每一列都是偶数。

① 0 ②

0 ④ ③

⑥ ⑤ 0

最后找不到就不需要再填，继续下一个即可（奇数是向上取整，偶数向下取整）。

如何实现？暴力模拟，参考Dinic算法的优化，用引用，保证只扫一遍——每一行只会循环查找n列、每一列只会循环查找n行。

（当然，如果考场上想不到，你也可以想一想怎么编数据，编数据的时候也会发现此规律。）

程序实现