[atARC156F]Make Same Set

考虑网络流，具体建图如下：

整张图共\(4\)层，用\((i,j)\)表示第\(i\)层的第\(j\)个点，则边集包含

• 从\(S\)向\((1,i)\)连流量为\(1\)的边
• 从\((1,i)\)向\((2,a_{i})\)和\((2,b_{i})\)连流量为\(1\)的边
• 从\((2,i)\)向\((3,i)\)连流量为\(1\)的边
• 从\((3,a_{i})\)和\((3,c_{i})\)向\((4,i)\)连流量为\(1\)的边
• 从\((4,i)\)向\(T\)连流量为\(1\)的边

但相比于原问题，上述做法并不能保证每个\(i\)均被选

具体的，从图上来看，即每个\(i\)均有\((2,a_{i})\rightarrow (3,a_{i})\)或\((2,b_{i})\rightarrow (3,b_{i})\)被流过

（另一侧根据对称性同理，以下不作考虑）

结论：若\(i\)满足该条件，则每次以最短路增广后（即Dinic），\(i\)仍满足该条件

记原来流过的为\((1,j)\rightarrow (2,x)\rightarrow (3,x)\)（其中\(x\in \{a_{i},b_{i}\}\)），并分类讨论：

• 若\(S\rightarrow (1,i)\)被流过，显然其不会被退流，根据流量守恒满足条件
• 若\(j=i\)，即此次增广流过\((1,i)\)，则之后还流过\((1,i)\rightarrow (2,y)\rightarrow (3,y)\)
• 若\(j\ne i\)，则不会流过\((3,x)\rightarrow (2,x)\)，因为直接流\(S\rightarrow (1,i)\rightarrow (2,x)\rightarrow (1,j)\)更短

在此基础上，初始使所有\(i\)均满足条件即可，简单的构造即均选\(a_{i}\)

由于是类似二分图的结构，时间复杂度为\(O((n+V)\sqrt{n})\)（其中\(V\)为值域）

#include<bits/stdc++.h>
using namespace std;
const int N=5005,M=10005;
int n,m,ans,a[N],b[N],c[N],pos[M],vis[N];
namespace Dinic{
	const int N=30005,M=40005;
	int S,T,E,ans,head[N],Head[N],d[N];
	queue<int>q;
	struct edge{
		int nex,to,len;
	}e[M<<1];
	void init(){
		E=0;
		memset(head,-1,sizeof(head));
	}
	void add(int x,int y,int z){
		e[E]=edge{head[x],y,z},head[x]=E++;
		e[E]=edge{head[y],x,0},head[y]=E++;
	}
	bool bfs(){
		memset(d,-1,sizeof(d));
		d[S]=0,q.push(S);
		while (!q.empty()){
			int k=q.front();q.pop();
			for(int i=head[k];i!=-1;i=e[i].nex){
				int u=e[i].to;
				if ((e[i].len)&&(d[u]<0))d[u]=d[k]+1,q.push(u);
			}
		}
		return d[T]>=0;
	}
	int dfs(int k,int s){
		if (k==T)return s;
		int ans=0;
		for(int &i=head[k];i!=-1;i=e[i].nex){
			int u=e[i].to;
			if ((e[i].len)&&(d[u]==d[k]+1)){
				int p=dfs(u,min(s,(int)e[i].len));
				e[i].len-=p,e[i^1].len+=p,s-=p,ans+=p;
				if (!s)return ans;
			}
		}
		return ans;
	}
	int query(int s,int t){
		S=s,T=t,ans=0;
		memcpy(Head,head,sizeof(head));
		while (bfs()){
			ans+=dfs(S,1e9);
			memcpy(head,Head,sizeof(head));
		}
		return ans;
	}
};
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)scanf("%d",&b[i]);
	for(int i=1;i<=n;i++)scanf("%d",&c[i]);
	for(int i=1;i<=n;i++)m=max(m,max(max(a[i],b[i]),c[i]));
	for(int i=1;i<=n;i++)pos[a[i]]=i;
	for(int i=1;i<=m;i++)
		if (pos[i])ans++,vis[pos[i]]=1;
	Dinic::init();
	for(int i=1;i<=m;i++){
		if (!pos[i])Dinic::add(n+i,n+m+i,1);
		else Dinic::add(n+m+i,n+i,1);
	}
	for(int i=1;i<=n;i++){
		if (!vis[i]){
			Dinic::add(0,i,1);
			Dinic::add(i,n+a[i],1),Dinic::add(i,n+b[i],1);
			Dinic::add(n+(m<<1)+i,(n+m<<1)+1,1);
			Dinic::add(n+m+a[i],n+(m<<1)+i,1),Dinic::add(n+m+c[i],n+(m<<1)+i,1);
		}
		else{
			Dinic::add(i,0,1);
			Dinic::add(n+a[i],i,1),Dinic::add(i,n+b[i],1);
			Dinic::add((n+m<<1)+1,n+(m<<1)+i,1);
			Dinic::add(n+(m<<1)+i,n+m+a[i],1),Dinic::add(n+m+c[i],n+(m<<1)+i,1);
		}
	}
	printf("%d\n",Dinic::query(0,(n+m<<1)+1)+ans);
	for(int i=1;i<=m;i++)
		if ((pos[i]>0)==Dinic::e[i-1<<1].len)printf("%d ",i);
	return 0;
}