题解：CF1783F Double Sort II

Drink_Assam · 2026-08-11 11:20:10 · 题解

先考虑只有一个排列时怎么做。建图，对于所有 a_i 都连边 i\rarr a_i 代表一次交换操作，交换排列上的数即交换结点（以它们为起点的边改变起点但终点不变）。最后的图一定是由若干个环形成。那么对于每一个环，按执行每一条边的操作，最后一次操作必然是自环的操作没有意义，所以对答案的贡献为环长减 1。

如果是两个排列，建两张图。一次操作即在两张图中选择同一个点，对于两张图中指向它的边，交换边两端的点。要是答案尽量小，即需使两张图中最后自环的点尽量重合。无论是哪张图，每次选择的点在操作后一定会变成自环所以每个点。也就是说，可以尽可能多地选点，使得它们不被操作，唯一条件是每个环最多选一个点。

记录每个点在两张图中对应的环编号。如果选出一个点，那么它所在的两个环都不能选其他点。那就再建一个图，对于每个点把它所在的两个环连边，最后要选出尽可能多的边使得每个点最多选一个邻边，也就是二分图最大匹配。答案就是总环数减最大匹配数。