ARC156F Make Same Set 做题记录

给定三个长 $n$ 的序列 $A,B,C$，找到一个符合以下条件且大小最大的集合 $S$：

• 其能被这样生成：对于每个 $i\in [1, n]$，向 $S$ 中加入 $A_i$ 或者 $B_i$；
• 其能被这样生成：对于每个 $i\in [1, n]$，向 $S$ 中加入 $A_i$ 或者 $C_i$；

需要输出方案。

$1\le n\le 5000$，$1\le A_i,B_i,C_i\le 10000$。

考虑弱化限制，如果给每次操作增加一个“什么都不做”的选项，那么可以直接跑最大流。

具体的，可以建四排点，所有边流量都是 $1$：（图来自 Schi2oid 的题解）

这样做的问题是跑完最大流后有可能存在某些第二排或者倒数第二排的点实际上什么都没做，即它们对应的出边/入边中没有点被流经。不妨称这些点为“空点”。

考虑不断跑流的过程中什么时候会增加新的“空点” $u$，先来考虑 $u$ 在第二排的情况（在倒数第二排同理）。显然不可能同时退掉 $u$ 的两个出点，故一定是退掉了 $u$ 的一个出点 $x$。

那么退流之前 $S\to u$ 的边肯定没满流，否则 $u$ 流向了 $x$，这次退流一定会经过 $u$，则 $u$ 不会变成“空点”。

那么一定可以将 $S\to ...\to x$ 这一段路径直接换成 $S\to u\to x$，这样增广路的长度必定会变短，而 $u$ 将不再是“空白点”。

所以每次找最短的增广路去增广就一定不会使“空白点”变多。

注意到 dinic 每次找的增广路就是最短的，所以先钦定每次都选择 $A_i$，再跑 dinic 即可。

代码如下：

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

const int S=300005,V=10000,inf=1e8;

int n,A[S],B[S],C[S];
int vis[S],idx[S];
int esum=1,to[S],c[S],nxt[S],h[S];
int s,t;
int dep[S],cur[S];

inline void added(int x,int y,int w)
{
	to[++esum]=y;
	c[esum]=w;
	nxt[esum]=h[x];
	h[x]=esum;
}

inline void add(int x,int y,int w)
{
	added(x,y,w),added(y,x,w^1);
}

inline bool bfs()
{
	for(int i=s;i<=t;i++) dep[i]=0,cur[i]=h[i];
	queue<int> q;
	dep[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=h[u];i;i=nxt[i])
		{
			int v=to[i],w=c[i];
			if(w>0&&dep[v]==0)
			{
				dep[v]=dep[u]+1;
				q.push(v);
			}
		}
	}
	return dep[t]>0;
}

int dfs(int u,int w)
{
	if(u==t) return w;
	int sum=0;
	for(int &i=cur[u];i;i=nxt[i])
	{
		if(c[i]==0) continue;
		int v=to[i];
		if(dep[v]!=dep[u]+1) continue;
		int r=dfs(v,min(c[i],w));
		c[i]-=r;
		c[i^1]+=r;
		w-=r;
		sum+=r;
		if(w==0) break;
	}
	if(sum==0) dep[u]=0;
	return sum;
}

inline int dinic()
{
	int res=0;
	while(bfs()) res+=dfs(s,inf);
	return res;
}

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]);
	s=0,t=n*2+V*2+1;
	int res=0;
	for(int i=1;i<=n;i++)
	{
		int x=1;
		if(vis[A[i]]==0)
		{
			vis[A[i]]=1;
			res++;
			x=0;
		}
		add(s,i,x);
		add(n+i,t,x);
		add(i,n*2+A[i],x);
		add(i,n*2+B[i],1);
		add(n*2+V+A[i],n+i,x);
		add(n*2+V+C[i],n+i,1);
	}
	for(int i=1;i<=V;i++) add(n*2+i,n*2+V+i,vis[i]^1),idx[i]=esum;
	res+=dinic();
	printf("%d\n",res);
	for(int i=1;i<=V;i++) if(c[idx[i]]>0) printf("%d ",i);
	printf("\n");
	return 0;
}