[AT5203][AGC038F]Two Permutations(网络流).md
题面
给出两个排列(P,Q).要求构造两个排列(A,B).
要求:(A_i)要么等于(i),要么等于(P_i);(B_i)要么等于(i),要么等于(Q_i)
最大化(A_i
eq B_i)的下标(i)数量
分析
注意原题的排列是从0开始的,为讨论方便,我们统一转化为从1开始的。
考虑对于每个排列,把(i)向(P_i)连边,那么就会形成很多个环。比如排列({3,2,4,1}),其中(3,4,1)和(2)分别形成两个环(1-3-4-1)和(2-2)。我们令(A_i=P_i),实际上就是把环上的数(P_i)选转过来(当然理解成把(i)转过来也可以,只是环上点权设置的问题).令(A_i=i)就是不旋转。对于一个环，环上的点选择的方案应该是一致的(全都等于(i)或全都不等于(i)),否则就会存在某个数不合法。
因为每个环只能选择旋转或不旋转,这就成了一个用最小割表示冲突的建图题,类似[LuoguP4313] 文理分科.我们把每个环看成一个点,记(idp_i)为(P_i)在哪个环上,(idq_i)为(Q_i)在哪个环上。
我们尝试让割的大小为(A_i=B_i)的下标数量,这样n-最小割就是答案。p分入S集合表示旋转,q分入T集合表示旋转.
- 若(P_i=Q_i),无论如何(A_i=B_i),不连边,直接令答案-1.
- 若(P_i=i,Q_i eq i),(idq_i)不能旋转,连边((idq_i,T,1)),割去这条边表示(idq_i)不旋转
- 若(P_i eq i,Q_i=i),(idp_i)不能旋转,连边((S,idp_i,1)),割去这条边表示(idp_i)不旋转
- 若(P_i eq i,Q_i eq i),(idp_i,idq_i)都不能旋转,连边((q_i,p_i,1)),割去这条边表示(idp_i,idq_i)都不能旋转
- 若(P_i=Q_i eq i),(idp_i,idq_i)可以同时旋转或不旋转,连边((q_i,p_i,1))和((p_i,q_i,1))表示两种选择
因为建出的图是二分图。时间复杂度(O(nsqrt n))略微卡常,记得Dinic要加当前弧优化
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define INF 0x3f3f3f3f
#define maxn 200000
#define maxm 1000000
using namespace std;
template<typename T> void qread(T &x){
x=0;
T sign=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') sign=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-'0';
c=getchar();
}
x=x*sign;
}
struct edge{
int from;
int to;
int next;
int flow;
}E[maxm*2+5];
int sz=1;
int head[maxn+5];
int cur[maxn+5];//当前弧优化
void add_edge(int u,int v,int w){
// printf("%d->%d %d
",u,v,w);
sz++;
E[sz].from=u;
E[sz].to=v;
E[sz].next=head[u];
E[sz].flow=w;
head[u]=sz;
sz++;
E[sz].from=v;
E[sz].to=u;
E[sz].next=head[v];
E[sz].flow=0;
head[v]=sz;
}
int deep[maxn+5];
bool bfs(int s,int t){
for(int i=s;i<=t;i++) deep[i]=0;
queue<int>q;
q.push(s);
deep[s]=1;
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=E[i].next){
int y=E[i].to;
if(E[i].flow&&!deep[y]){
deep[y]=deep[x]+1;
q.push(y);
}
}
}
return deep[t]>0;
}
int dfs(int x,int t,int minf){
if(x==t) return minf;
int rest=minf,k;
for(int &i=cur[x];i;i=E[i].next){
int y=E[i].to;
if(E[i].flow&&deep[y]==deep[x]+1){
k=dfs(y,t,min(rest,E[i].flow));
E[i].flow-=k;
E[i^1].flow+=k;
rest-=k;
if(k==0) deep[y]=0;
if(rest==0) break;
}
}
return minf-rest;
}
int dinic(int s,int t){
int ans=0,now=0;
while(bfs(s,t)){
for(int i=s;i<=t;i++) cur[i]=head[i];
while((now=dfs(s,t,maxm+1))) ans+=now;
}
return ans;
}
int n;
int p[maxn+5],q[maxn+5];
int cnt=0;//环个数
int idp[maxn+5],idq[maxn+5];//所在环编号
void mark(int *id,int *a,int x){
while(!id[x]){
id[x]=cnt;
x=a[x];
}
}
int main(){
qread(n);
for(int i=1;i<=n;i++){
qread(p[i]);
p[i]++;
}
for(int i=1;i<=n;i++){
qread(q[i]);
q[i]++;
}
for(int i=1;i<=n;i++){//找出每个环
if(!idp[i]){
cnt++;
mark(idp,p,i);
}
}
for(int i=1;i<=n;i++){
if(!idq[i]){
cnt++;
mark(idq,q,i);
}
}
int s=0,t=cnt+1;
int eq=0;//相等的个数
for(int i=1;i<=n;i++){
if(p[i]==i&&q[i]==i) eq++;
else if(p[i]==i&&q[i]!=i) add_edge(idq[i],t,1);
else if(p[i]!=i&&q[i]==i) add_edge(s,idp[i],1);
else if(p[i]!=q[i]) add_edge(idq[i],idp[i],1);
else{
add_edge(idq[i],idp[i],1);
add_edge(idp[i],idq[i],1);
}
}
eq+=dinic(s,t);
printf("%d
",n-eq);
}