Grid Puzzle II

题目描述

有一个 n \times n 的方格，每个格子里都有一些金币。 你知道每一行和每一列必须从该行或该列中选择多少个格子。你从每个被选择的格子里获得所有的金币。你最多能收集多少金币，并且如何选择格子以满足给定的条件？

输入格式

第一行输入一个整数 n：方格的大小。行和列编号为 1,2,\dots,n。 下一行有 n 个整数 a_1,a_2,\ldots,a_n：你必须从第 i 行恰好选择 $a_i$ 个格子。 再下一行有 n 个整数 b_1,b_2,\ldots,b_n：你必须从第 j 列恰好选择 $b_j$ 个格子。 最后，有 n 行描述该网格。你可以假设 $a_1+a_2+\dots+a_n$ 与 $b_1+b_2+\dots+b_n$ 相等。

输出格式

首先输出一个整数 k：你最多能收集的金币数。之后输出 n 行描述你选择了哪些格子（X 表示你选择了该格子，. 表示你没有选择该格子）。 如果无法满足条件，则只输出 -1。

5
0 1 3 2 0
1 2 2 0 1
2 5 1 5 1
0 2 5 1 2
3 8 9 3 5
1 4 3 7 3
0 3 6 2 8

32
.....
..X..
.XX.X
XX...
.....

提示

$1 \le n \le 50$ $0 \le a_i \le n$ $0 \le b_j \le n$ $0 \le c_{ij} \le 1000$

标签: CSES2131|附加题2

来源

CSES2131|附加题2