← 返回题目列表

AtCoder · practice2_e

E. 最小成本流程

中文机器翻译题面 查看原题

分数: 100 点

问题陈述

给你一个网格 N 行和 M 列。广场位于 i第行和 j第列将表示为 (i,j)。 非负整数 每个方格都写有 A_{i,j} 为每个方块写 (i,j).

你选择一些方格,使得每行和每列最多包含 K 选定的方块。 在此约束下,计算写在所选方格上的整数之和的最大值。 此外,计算一种选择达到最大值的方格的方法。

约束

  • 1 \leq N \leq 50
  • 1 \leq K \leq N
  • 0 \leq A_{i,j} \leq 10^9
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N K
A_{1,1} A_{1,2} \cdots A_{1,N}
A_{2,1} A_{2,2} \cdots A_{2,N}
\vdots
A_{N,1} A_{N,2} \cdots A_{N,N}

输出

在第一行,打印所选方格上写入的整数之和的最大值。

上下 N 行,打印达到最大值的方式。

准确地说,输出字符串 t_1,t_2,\cdots,t_N,满足 t_{i,j}=X 如果您选择 (i,j) 和 t_{i,j}=. 否则。

您可以通过任何方式打印来选择使总和最大化的方块。


示例输入 1

3 1
5 3 2
1 4 8
7 6 9

示例输出 1

19
X..
..X
.X.

示例输入 2

3 2
10 10 1
10 10 1
1 1 10

示例输出 2

50
XX.
XX.
..X