[图论记录]AT5203 [AGC038F] Two Permutations

**题意** ： 给出两个长度为 $n$ 的排列 $P,Q$。 构造两个**排列** $A,B$ ，其中 ： - $A_i$ 为 $i$ 或 $P_i$。 - $B_i$ 为 $i$ 或 $Q_i$。 求 $\sum_{i=1}^n[A_i\neq B_i]$ 的最大值。 $n\leq 10^5$ ，时限$\texttt{8s}$。 ------------ 观察序列 $A$ 和 $P$ 之间的关系，不难发现，对于 $P$ 中的某个环，要么原封不动，要么全部选择 $A_i=i$。 我们可以对每个环分别决策。称“选择”环 $a$ 表示将 $a$ 中的 $A_i\leftarrow i$。 考虑环之间的贡献模式。 对于位置 $i$ ，在 $P$ 中被环 $p$ 包含，$Q$ 中被环 $q$ 包含。 - $P_i=Q_i=i$ ： 贡献必然为 $0$。 - $P_i\neq i,Q_i=i$ ：不选 $p$ 时贡献 $1$。 - $P_i=i,Q_i\neq i$ ：不选 $q$ 时贡献 $1$。 - $P_i\neq i,Q_i\neq i,P_i\neq Q_i$ ：不同时选 $p,q$ 时贡献 $1$。 - $P_i\neq i,Q_i\neq i,P_i= Q_i$ ：$p,q$ 单选一个时贡献 $1$。 我们发现这些条件有点复杂……这是因为 $A_i\neq B_i$ 对应的情况较多，反过来最小化 $\sum_{i=1}^n[A_i=B_i]$ ，需要考虑的情况就较少了。 - $P_i=Q_i=i$ ： 贡献必然为 $1$。 - $P_i\neq i,Q_i=i$ ：选 $p$ 时贡献 $1$。 - $P_i=i,Q_i\neq i$ ：选 $q$ 时贡献 $1$。 - $P_i\neq i,Q_i\neq i,P_i\neq Q_i$ ：同时选 $p,q$ 时贡献 $1$。 - $P_i\neq i,Q_i\neq i,P_i= Q_i$ ：$p,q$ 同时选或同时不选时贡献 $1$。 观察到每个环只有“选和不选”两种情况，这启发我们用最小割求解。 对于 $P$ 中的环 $p$ ，若分入 $S$ 集代表选，分入 $T$ 集代表不选。 对于 $P$ 中的环 $p$ ，若分入 $S$ 集代表不选，分入 $T$ 集代表选。 刚好是反过来的。注意到条件中要求 $p,q$ 同时选或不选，通过刻意地取反，选法相同的 $p,q$ 会被分割在不同的集合中，产生割。 （如何让割管理 $p,q$ 在同一个集合的情况？将一侧的状态取反！） 下面是每种情况对应的连边方法 ： - 不连边，但答案加一。 - $p\rightarrow T$ ，若选 $p$ （$p\in S$），则需要割掉这条边。 - $S\rightarrow q$ ，若选 $q$ （$q\in T$），则需要割掉这条边。 - $p\rightarrow q$ ，同时选 $p,q$ （$p\in S,q\in T$），则需要割掉这条边。 - $p\rightarrow q,\ q\rightarrow p$ ， $p\rightarrow q$ 的作用和上一条相同。同时不选 $p,q$ （$p\in T,q.in S$），则需要割掉 $q\rightarrow p$。 Dinic 求解类二分图匹配，复杂度为 $O(n\sqrt{n})$。 ```cpp #include<algorithm> #include<cstdio> #include<queue> #define MaxN 200500 using namespace std; const int INF=1000000000; struct Line{int t,cap,nxt;}l[MaxN<<3]; int fir[MaxN],tl=1; void adl(int u,int v,int cap){ l[++tl]=(Line){v,cap,fir[u]};fir[u]=tl; l[++tl]=(Line){u,0,fir[v]};fir[v]=tl; } int S,T,cur[MaxN],dis[MaxN]; queue<int> q; bool bfs() { for (int i=1;i<=T;i++) {dis[i]=-1;cur[i]=fir[i];} dis[S]=0;q.push(S); while(!q.empty()){ int u=q.front();q.pop(); for (int i=fir[u];i;i=l[i].nxt) if (l[i].cap&&dis[l[i].t]==-1){ dis[l[i].t]=dis[u]+1; q.push(l[i].t); } }return dis[T]!=-1; } int dfs(int u,int flow) { if (u==T)return flow; int sum=0; for (int &i=cur[u],v;i;i=l[i].nxt) if (l[i].cap&&dis[v=l[i].t]==dis[u]+1){ int now=dfs(v,min(flow-sum,l[i].cap)); sum+=now; l[i].cap-=now; l[i^1].cap+=now; if (flow-sum==0)return sum; } if (!sum)dis[u]=-1; return sum; } int n,tn,p1[MaxN],p2[MaxN],v1[MaxN],v2[MaxN]; int main() { scanf("%d",&n); for (int i=1;i<=n;i++){scanf("%d",&p1[i]);p1[i]++;} for (int i=1;i<=n;i++){scanf("%d",&p2[i]);p2[i]++;} for (int i=1;i<=n;i++)if (!v1[i]){ v1[i]=++tn; for (int p=p1[i];p!=i;p=p1[p])v1[p]=tn; } for (int i=1;i<=n;i++)if (!v2[i]){ v2[i]=++tn; for (int p=p2[i];p!=i;p=p2[p])v2[p]=tn; } S=tn+1;T=S+1; int ans=0; for (int i=1;i<=n;i++){ if (p1[i]==i&&p2[i]==i)ans++; if (p1[i]!=i&&p2[i]==i)adl(v1[i],T,1); if (p1[i]==i&&p2[i]!=i)adl(S,v2[i],1); if (p1[i]!=i&&p2[i]!=i){ adl(v1[i],v2[i],1); if (p1[i]==p2[i])adl(v2[i],v1[i],1); } } while(bfs())ans+=dfs(S,INF); ans=n-ans; printf("%d",ans); return 0; } ```