Sorting a Grid

怎么洛谷又没了。

怕下次又忘了所以写。

习惯了谎话，早已分不清真假。

不妨给 D 的每一行染一个颜色，那么 C 每一行的是一种颜色即可。

可以发现有 \(n\) 种颜色，每种颜色数量为 \(m\)。每一行颜色不是一样的。

考虑 B 如何一定合法。显然每一列不能有重复元素，等价于每一列有 m 种元素。

考虑 A 变到 B，也就是每次有一堆颜色可重集 \(S\)，给 \(S\) 中的每个元素分配一个列。

发现这个东西根本就不可做啊。（不好让同颜色不在同一列）

既然列的限制比较多，我们不妨考虑扫描每一列来计算。计算时，颜色和行一一匹配，可以建立二分图。

具体来说，你知道每一行还有哪些颜色，你直接建边然后二分图最大匹配即可。显然是完美的。

匹配完了过后你把匹配上的这一列的颜色的边删掉即可。现在我们只需要解决这样子是否可能导致无解。

其实我不想解释，因为不会。