Description
给定两个 \(0-(N-1)\) 的排列 \(\left\{P_{i}\right\}\) 和 \(\left\{Q_{i}\right\}\) 。要求构造两个 \(0-(N-1)\) 的排列 \(\left\{A_{i}\right\}\) 和 \(\left\{B_{i}\right\}\), 且满足对 \(\forall 0 \leq i<N, A_{i}=P_{i}\) 或 \(i, B_{i}=Q_{i}\) 或 \(i\) 。
要求最大化 \(A_{i} \neq B_{i}\) 的数量, 输出这个最大值。
\(1\le n\le 10^5\)。
Solution
声明：拆环指的是当前位置选择 \(i\) 而不是 \(P_i\) 或者 \(Q_i\)。
考虑将 \(P\) 中的循环看做一个整体，因为发现，如果对于环上任意一个位置，将其拆掉，可以推导得出整个环都会被拆。\(Q\) 同理。
同时根据正难则反的思想，将题目转换成出至少有多少个位置 \(A_i=B_i\)。
分情况讨论一下什么情况下会产生贡献：
- 当 \(P_i=Q_i=i\) 时，这种情况下无论什么情况 \(A_i=B_i\)，答案 -1 即可。
- 当 \(P_i=i,Q_i\not=i\) 时，将 \(Q_i\) 对应的环拆掉会产生贡献，否则不会。
- 当 \(P_i\not=i,Q_i=i\) 时，同上，将 \(P_i\) 对应的环拆掉才会产生贡献，否则不会。
- 当 \(P_i\not=i,Q_i\not=i,P_i\not=Q_i\) 时，同时拆掉两个环才会产生贡献，否则不会。
- 当 \(P_i\not=i,Q_i\not=i,P_i=Q_i\) 时，同时拆或者同时不拆都会产生贡献。
想到这里，网络流就呼之欲出（或许吧）。
将 \(P_i\) 对应的环放在左边， \(Q_i\) 对应的环放在右边，设源点 \(S\) 和汇点 \(T\)。
根据上述情况连边，连边如下（一一对应）：
- 不用连边，答案直接减。
- \(Q_i\) 对应的环向 \(T\) 连一条流量为 1 的边。
- \(S\) 向 \(P_i\) 对应的环连一条流量为 1 的边。
- \(Q_i\) 对应的环向 \(P_i\) 对应的环连流量为 1 的边。（避免出现产生一些不合法的答案）
- \(P_i\) 对应的环向 \(Q_i\) 对应的环连流量为 1 的边，\(Q_i\) 对应的环也向 \(P_i\) 对应的环连流量为 1 的边。（两条）
然后愉快的套上 \(\mathcal{Dinic}\) 就好了。
Code
#include<queue>
#include<cstdio>
#define N 100005
#define inf 2147483647
using namespace std;
struct node
{
int to,head,next,flow;
}a[N<<2];
int n,S,T,tot=1,cnt,ans,p[N],q[N],r1[N],r2[N],cur[N],deep[N];
bool bj1[N],bj2[N];
void getring1(int x)
{
++cnt;
while (!bj1[x]) r1[x]=cnt,bj1[x]=true,x=p[x];
}
void getring2(int x)
{
++cnt;
while (!bj2[x]) r2[x]=cnt,bj2[x]=true,x=q[x];
}
void add(int x,int y,int z)
{
a[++tot].to=y;a[tot].flow=z;a[tot].next=a[x].head;a[x].head=tot;
a[++tot].to=x;a[tot].flow=0;a[tot].next=a[y].head;a[y].head=tot;
}
bool bfs()
{
queue<int> q;
for (int i=1;i<=cnt;++i)
deep[i]=0;
q.push(S);deep[S]=1;
while (!q.empty())
{
int x=q.front();q.pop();
for (int i=a[x].head;i;i=a[i].next)
{
int v=a[i].to;
if (!deep[v]&&a[i].flow) deep[v]=deep[x]+1,q.push(v);
}
}
return deep[T]!=0;
}
int dfs(int x,int fl)
{
if (x==T) return fl;
int res=fl;
for (int i=cur[x];i;i=a[i].next)
{
int v=a[i].to;
cur[x]=i;
if (deep[v]==deep[x]+1&&a[i].flow)
{
int f=dfs(v,min(res,a[i].flow));
a[i].flow-=f;a[i^1].flow+=f;res-=f;
if (!res) break;
}
}
return fl-res;
}
int dinic()
{
int res=0;
while (bfs())
{
for (int i=1;i<=cnt;++i)
cur[i]=a[i].head;
res+=dfs(S,inf);
}
return res;
}
int main()
{
freopen("per.in","r",stdin);
freopen("per.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;++i)
scanf("%d",&p[i]),++p[i];
for (int i=1;i<=n;++i)
scanf("%d",&q[i]),++q[i];
for (int i=1;i<=n;++i)
if (!bj1[i])
getring1(i);
for (int i=1;i<=n;++i)
if (!bj2[i])
getring2(i);
S=++cnt;T=++cnt;
ans=n;
for (int i=1;i<=n;++i)
{
if (p[i]==q[i]&&p[i]==i) ans--;
else if (q[i]==i) add(S,r1[i],1);
else if (p[i]==i) add(r2[i],T,1);
else if (p[i]==q[i]) add(r2[i],r1[i],1),add(r1[i],r2[i],1);
else add(r2[i],r1[i],1);
}
printf("%d\n",ans-dinic());
return 0;
}