aeemnSttt
给定 \(p,q\) 两个排列，构造两个排列 \(a,b\)，满足 \(\forall i\)：
- \(a_i=i \lor a_i=p_i\)
- \(b_i=i \lor b_i=q_i\)
求序列 \(\sum [a_i \neq b_i]\) 的最大值。
\(n \le 10^5\)。
ilnooStu
将原问题以二分图形式描述限制（是排列），以 \(a\) 为例；
拆点 \(x,x'\)，\(x\) 代指下标，\(x'\) 代指值；
连接无向边：\((i,i'),(i,(p_i)')\)，选择一个匹配就等价于 \(a_i=i\) 或 \(p_i\)，隐含不能将一个值同时分配给多个下标。
总度数显然为 \(2n=\) 总点数，形成若干个偶环。每个偶环对应 \(2\) 种决策：使环内所有下标点 \(i\) 对应 \(a_i=i\) 或 \(a_i=p_i\)。为环编号 \(c\)，设环内节点集为 \(S_c\)。
以上为限制条件。
转化为求 \(a_i=b_i\) 最少。
| \(a\)\\(b\) | R | B |
|---|---|---|
| R | \(i,i\) | \(i,q_i\) |
| B | \(p_i,i\) | \(p_i,q_i\) |
最小割建模，令 \(a\) 在源点集合为 R，在汇点集合为 B，\(b\) 相反：
- \(i \neq p_i, i \neq q_i\)：
- \(p_i \neq q_i\)：RR；
- \(p_i = q_i\)：RR,BB；
- \(i \neq p_i, i = q_i\)：RR,RB；
- \(i = p_i, i\neq q_i\)：RR,BR；
- \(i=p_i,i=q_i\)：All；
连：
-
限制边：无需限制边，直接以环点 \(c\) 代替所有环上节点做决策。
-
考虑下标 \(i\)，在 \(a, b\) 对应环点分别为 \(x,y\)：
- 分情况：
- RR 会在此处产生贡献：\(y \to x,w=1\)；
- RR,BB 会在此处产生贡献：\(y \to x, w=1\)，\(x \to y,w=1\)；
- R_ 会在此处产生贡献：\(s \to x,w=1\)；
- _R 会在此处产生贡献：\(y \to t, w=1\)；
- 一定产生贡献：\(s\to t,w=1\)；
- 分情况：