P11717 [清华集训 2014] 矩阵变换 题解

· · 题解

神秘转化题。

前置知识：稳定婚姻问题。

解题思路

考虑对于一个任意排列 p，其不能作为一个合法答案的充要条件：\exist 1\leq i,j \leq n,A_{j,p_i}\gt A_{i,p_i},A_{j,p_j}\gt A_{j,p_i}，此时设 p_j \leftarrow p_i 一定是一个更优的答案。

钦定 \exist 1\leq i,j \leq n,A_{j,p_i}\gt A_{i,p_i},A_{j,p_j}\gt A_{j,p_i} 时 j 与 p_i 匹配称为更优匹配，不难发现 p 为一个答案的条件为 p 中不存在更优匹配。

注意到这个是稳定婚姻形式，考虑对每一行以及每个数钦定一个优先级。整理以上两个条件可以得到两个优先级：

根据这个倾向求得的匹配必定是一个合法解，根据稳定婚姻的有解性可以得知其必定存在合法解。

时间复杂度 O(TN^2\log N)。