【AGC038F】 Two Permutations

一个排列可以拆成很多个环，我们设 $P_i$ 属于的环为 $p_i$，$Q_i$ 属于的环为 $q_i$。

对于一个环，只有两种选择，拆成若干自环或保留原状。

我们发现情况分为 $5$ 种：

• $P_i=Q_i=i$，此时必然 $A_i=B_i$。
• $P_i=i,Q_i\ne i$，当且仅当 $q_i$ 被拆分时 $A_i=B_i$。
• $P_i\ne i,Q_i=i$，当且仅当 $p_i$ 被拆分时 $A_i=B_i$。
• $P_i\ne Q_i,P_i\ne i,Q_i\ne i$，当且仅当 $p_i$ 和 $q_i$ 都被拆分时 $A_i=B_i$。
• $P_i=Q_i\ne i$，当且仅当 $p_i$ 和 $q_i$ 都被拆分或都不被拆分时 $A_i=B_i$。

我们设 $p_i$ 被拆分时在 $S$ 集合中，$q_i$ 被拆分时在 $T$ 集合中，建出最小割模型。

• $P_i=Q_i=i$，必定耗费 $1$ 代价。
• $P_i=i,Q_i\ne i$，$q_i$ 在 $T$ 集合中耗费 $1$ 代价，$S$ 向 $q_i$ 连边权为 $1$ 的边。
• $P_i\ne i,Q_i=i$，$p_i$ 在 $S$ 集合中耗费 $1$ 代价，$p_i$ 向 $T$ 连边权为 $1$ 的边。
• $P_i\ne Q_i,P_i\ne i,Q_i\ne i$，$p_i$ 在 $S$ 且 $q_i$ 在 $T$ 耗费 $1$ 代价，$p_i$ 向 $q_i$ 连边权为 $1$ 的边。
• $P_i=Q_i\ne i$，$p_i$ 和 $q_i$ 在不同集合耗费 $1$ 代价，$p_i$ 和 $q_i$ 互连边权为 $1$ 的边。

然后跑最小割即可。 这里简单描述一下最后两种边为什么要这么连，以第四种情况为例，若 $S$ 能到 $p_i$，$q_i$ 能到 $T$，为了割开集合，就必须断这条边，也就是说只有断掉这条边才有可能 $p_i$ 在 $S$ 集合中，$q_i$ 在 $T$ 集合中。

因为是最小割，所以第五种情况的边在任何情况下最多只会割掉一个方向，所以代价是 $1$，没有问题。

然后是复杂度，由于是二分图单位边权，时间复杂度 $\mathrm O(n\sqrt n)$。

Submission #55948786 - AtCoder Grand Contest 038