CF1662J Training Camp

你正在组织一个训练营，教授小朋友们算法。有 $n^2$ 个小朋友，排列成 $n \times n$ 的方阵。每个小朋友的年龄在 $1$ 到 $n$ 岁（包含 $1$ 和 $n$），并且同一行或同一列的两个小朋友年龄都不相同。 你需要为一场编程比赛选出恰好 $n$ 个小朋友，每行每列各选一个。此外，未被选中的小朋友必须要么比其所在行和列被选中的小朋友都年长，要么都年幼（否则他们会抱怨）。注意，总是可以选出满足这些要求的 $n$ 个小朋友（例如选出 $n$ 个年龄相同的小朋友）。 在训练营期间，你发现有些小朋友擅长编程，有些则不擅长。你想知道，在满足所有要求的前提下，最多能选出多少个擅长编程的小朋友？

第一行包含一个整数 $n$（$1 \leq n \leq 128$），表示方阵的大小。 接下来的 $n$ 行描述小朋友的年龄。具体来说，第 $i$ 行包含 $n$ 个整数 $a_{i,1}, a_{i,2}, \dots, a_{i,n}$（$1 \leq a_{i,j} \leq n$），其中 $a_{i,j}$ 表示第 $i$ 行第 $j$ 列小朋友的年龄。保证同一行或同一列的两个小朋友年龄都不相同，即对于任意 $1 \leq i \leq n$，$1 \leq j < j' \leq n$，有 $a_{i,j} \ne a_{i,j'}$，对于任意 $1 \leq i < i' \leq n$，$1 \leq j \leq n$，有 $a_{i,j} \ne a_{i',j}$。 接下来的 $n$ 行描述小朋友的编程能力。具体来说，第 $i$ 行包含 $n$ 个整数 $c_{i,1}, c_{i,2}, \dots, c_{i,n}$（$c_{i,j} \in \{0, 1\}$），其中 $c_{i,j}=1$ 表示第 $i$ 行第 $j$ 列的小朋友擅长编程，$c_{i,j}=0$ 表示不擅长。

输出一个整数，表示在满足所有要求的前提下，最多能选出多少个擅长编程的小朋友。

在第一个样例中，无法同时选中两个擅长编程的小朋友（分别在第 $1$ 行第 $1$ 列和第 $2$ 行第 $3$ 列），因为那样的话你必须选中第 $3$ 行第 $2$ 列的小朋友，这样会有两个小朋友抱怨（第 $1$ 行第 $2$ 列和第 $3$ 行第 $1$ 列）。 一种包含 $1$ 个擅长编程小朋友的合法选择是选出所有年龄为 $1$ 岁的小朋友。 在第二个样例中，有 $10$ 种合法的选择方式，每种都能选出恰好 $2$ 个擅长编程的小朋友。 由 ChatGPT 4.1 翻译