AGC038F Two Permutations

题意 ： 给出两个长度为 的排列 。

构造两个排列 ，其中：

• 为 或 。
• 为 或 。

求 的最大值。

，时限 。

---

观察序列 和 之间的关系，不难发现，对于 中的某个环，要么原封不动，要么全部选择 。

我们可以对每个环分别决策。称“选择”环 表示将 中的 。

考虑环之间的贡献模式。

对于位置 ，在 中被环 包含， 中被环 包含。

• ： 贡献必然为 。

• ：不选 时贡献 。

• ：不选 时贡献 。

• ：不同时选 时贡献 。

• ： 单选一个时贡献 。

我们发现这些条件有点复杂……这是因为 对应的情况较多，反过来最小化 ，需要考虑的情况就较少了。

• ： 贡献必然为 。

• ：选 时贡献 。

• ：选 时贡献 。

• ：同时选 时贡献 。

• ： 同时选或同时不选时贡献 。

观察到每个环只有“选和不选”两种情况，这启发我们用最小割求解。

对于 中的环 ，若分入 集代表选，分入 集代表不选。

对于 中的环 ，若分入 集代表不选，分入 集代表选。

刚好是反过来的。注意到条件中要求 同时选或不选，通过刻意地取反，选法相同的 会被分割在不同的集合中，产生割。

（如何让割管理 在同一个集合的情况？将一侧的状态取反！）

下面是每种情况对应的连边方法 ：

• 不连边，但答案加一。

• ，若选 （），则需要割掉这条边。

• ，若选 （），则需要割掉这条边。

• ，同时选 （），则需要割掉这条边。

• ， 的作用和上一条相同。同时不选 （），则需要割掉 。

Dinic 求解类二分图匹配，复杂度为 。