7449. 网格谜题 II (Grid Puzzle II)
时间限制：1000 MS 内存限制：512 MB
题目描述
# 网格谜题 II (Grid Puzzle II) 时间限制：$1.00\text{ s}$ 空间限制：$512\text{ MB}$ ## 题目描述 有一个 $n \times n$ 的网格，其中每个格子都有一定数量的硬币。 你已知对于每一行和每一列，你分别必须从中选择多少个格子。你选中的每一个格子中的所有硬币都将被你收集。 请问你最多能收集到多少硬币，以及你应该如何选择格子以满足给定的约束？ ## 输入格式 第一行包含一个整数 $n$：网格的大小。行和列的编号分别为 $1, 2, \dots, n$。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$：你必须从第 $i$ 行中恰好选出 $a_i$ 个格子。 第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$：你必须从第 $j$ 列中恰好选出 $b_j$ 个格子。 接下来有 $n$ 行描述网格。你可以假设 $a_1, a_2, \dots, a_n$ 的总和与 $b_1, b_2, \dots, b_n$ 的总和相等。每一行包含 $n$ 个非负整数，代表格子中的硬币数。 ## 输出格式 首先输出一个整数 $k$：你可以收集到的最大硬币数量。 接下来输出 $n$ 行，描述你的选择（`X` 表示你选择该格子，`.` 表示你不选择该格子）。 如果无法满足条件，只需输出 `-1`。 ## 输入输出样例 ### 输入 #1 ```text 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 ``` ### 输出 #1 ```text 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$ （其中 $c_{ij}$ 表示第 $i$ 行第 $j$ 列的格子拥有的硬币数）