CF 1500 C

CF 1500 C
题意：

? 给你两个 \(n \times m\) 的矩阵 A,B（1 \(\leq\) n,m \(\leq\) 1500），矩阵的元素均为 [1,n] 内的整数。

? 每一次操作你可以选定一列作为每一行的关键字，按照关键字从小到大的顺序把所有行排序得到一个新矩阵。这里使用的排序是稳定的，即如果有两行的关键字相同，则按照在原矩阵的先后顺序排序。

你可以进行不超过 5000 次操作，问你能否将 A 变成 B。不能变成输出 ?1，否则输出一种可行的操作序列。

?
题解：

? 首先考虑由于排序是稳定的，那么我们一定可以确定 A 中的每一行最后对应着 B 的哪一行，(当然对应不起来就 -1 了)

? 现在考虑处理出来一个数组 p[i] 表示 B 的第 i 行是 A 的第 p[i] 行，那么可以发现，我们最后要让 p[i] 到第 i 个位置上，设 pos[i] 为 A的第 i 行所在位置，即要求 \(\forall\) pos[p[i]]

? 那么考虑对于每一列的操作，如果在该列 k 中 A(p[i],k) < A(p[i+1],k)，那么无事发生，如果存在 A(p[i],k) > A(p[i+1],k) ，那么如果操作该列，一定需要在后面有一个使得 p[i],p[i+1] 再交换回来的操作，即有一个操作 j 中 A(p[i],j) < A(p[i+1],j)

? 那么一个图论模型 自然 出现了，如果一个操作 x 中所有的 A(p[i],x) <= A(p[i+1],x)，那么贪心的我们肯定用这个操作，因为不会变劣，即 x 向 每个 A(p[i],x) < A(p[i+1],x) 的 i 连边，代表 x 操作后 i 就被 “解放” 了，而如果存在 A(p[i],x) > A (p[i+1],x) ，那么要求就是这些 i 在之后的操作中会被反过来，即 i 向 x 连边，代表所有的这种 i 被解放后 x 才能被释放掉。跑一遍拓扑排序，倒序输出方案。