CF1713E Cross Swapping 做题记录

给定一个 $n\times n$ 的矩阵。一次操作可以给定一个 $k$ 然后交换所有的 $A_{i,k}$ 和 $A_{k,i}$ 。

如图表示 $n=4,k=3$ 的情况。

求若干次操作后字典序最小的矩阵。

$1 \leq n \leq 1000$。

显然一个位置 $(x,y)$ 上的数只能被交换到 $(y,x)$，并且当且仅当 $k=x$ 和 $k=y$ 操作的执行状态不同才会被交换。

发现字典序最小肯定是尽量让前面的位置上的数更小，那么按照 $x,y$ 升序的顺序遍历所有满足 $x<y$ 的位置 $(x,y)$，若 $a_{x,y}<a_{y,x}$ 显然是让 $k=x$ 和 $k=y$ 操作的执行状态相同更优，否则不同更优。

考虑维护“两个操作的执行状态相同/不同”这个东西，显然可以考虑把 $k=x$ 操作拆成两个点 $x$ 和 $x+n$，用并查集维护。遍历到 $(x,y)$ 时，若 $k=x$ 和 $k=y$ 操作的执行状态相同，那么合并 $x,y$ 和 $x+n,y+n$ 所处的集合，否则合并 $x,y+n$ 和 $x+n,y$ 所处的集合。注意若 $x$ 和 $y+n$ 处于一个集合即 $k=x$ 和 $k=y$ 操作的执行状态不同前面的更优那么就不能合并 $x,y$ 和 $x+n,y+n$ 所处的集合；$x$ 和 $y$ 处于一个集合同理。

最后再按照 $x,y$ 升序的顺序遍历所有满足 $x<y$ 的位置 $(x,y)$，若 $x$ 和 $y+n$ 在同一个集合即 $k=x$ 和 $k=y$ 操作的执行状态不同那么交换 $a_{x,y}$ 和 $a_{y,x}$，即可找到答案。