自动搬运

查看原文

来自洛谷，原作者为

	linfourxu もうトサカに来たぜ

搬运于2025-08-24 21:47:35，当前版本为作者最后更新于2021-06-20 20:47:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道网络流建模+贪心求割边边集好题。

从数据范围以及求最长上升子序列相关，不难想到这道题。

具体的，考虑用一个流量来表示一个最长上升子序列。

一个较为显然的结论是，求出 $\text{dp}[i]$ 表示以 $i$ 为结尾的最长上升子序列的长度后，$i$ 这个位置在最长上升序列中只能位于第 $\text{dp}[i]$ 个位置显然很显然，即我们的最长上升子序列的下标序列 $\text{pos}$ 一定满足 $\text{dp}[\text{pos}[i]]=i$。

那么如果我们将所有的点满足 $i<j$ 且 $\text{dp}[i]=\text{dp}[j]-1$ 的位置 $(i,j)$ 建立一条由 $i$ 指向 $j$ 的边，令最长上升子序列的长度为了 $\text{len}$，那么任意一条最长上升子序列就可以表示为一条从 $\text{dp}[s]=1$ 的点到 $\text{dp}[t]=\text{len}$ 的点的一条路径，而回到这题的要求便是破坏所有的这种路径。

容易发现这题允许破坏的是”点“，那么最终的建图也基本明朗了起来。

1.将这 $n$ 个点拆为两个点即入点和出点，并将每个入点向对应出点连一条流量为 $B[i]$ 的边，表示破坏掉这个点的代价是 $B[i]$，也就是这题中，我们用”最小割“来表示“最小的破坏代价”。

2.将所有满足 $\text{dp}[i]=1$ 的点，建立一条由源点 $\text{S}$ 到 $i$ 入点的，流量为 $\text{inf}$ 的边；将所有满足 $\text{dp}[j]=\text{len}$ 的点，建立一条由 $j$ 出点到 汇点 $\text{T}$ 的，流量为 $\text{inf}$ 的边。

3.将所有的点满足 $i<j$ 且 $\text{dp}[i]=\text{dp}[j]-1$ 的位置 $(i,j)$ 建立一条由 $i$ 出点指向 $j$ 入点的，流量为 $\text{inf}$ 的边。这样一条条形如 $\text{S}$ -> $\text{pos}[1]$入点 -> $\text{pos}[1]$出点 -> $\text{pos}[2]$入点 -> $\text{pos}[2]$出点 -> $\dots$ -> $\text{pos}[\text{len}]$入点 -> $\text{pos}[\text{len}]$出点 -> $\text{T}$ 的增广路即为一条条最长上升子序列。而流量为 $\text{inf}$ 则表示不可破坏，实际上也就是我们只允许破坏每条"入点连向对应出点的边“。

最后跑一遍 $\text{S}$ 到 $\text{T}$ 的最小割即可求出第一问的最小代价。

再考虑如何确定出附加属性字典序最小的最小割割边边集。

首先容易发现的是，成为割边的一定是”入点连向对应出点的边“，这显然是我们一手策划的，将题目中的 $C$ 数组 $\text{sort}$ 之后，按顺序考虑每条边是否可能成为割边，如果可能的话就强制钦定它为割边。

具体实现的时候也不需要其他题解那么麻烦，判断一条边是否为割边，显然就是从该边的入点无法到达出点（当然不走流量为 $0$ 的边），代码实现上只需要调用一遍 $\text{dinic}$ 中的 $\text{bfs}$ 函数即可。而强制钦定他为割边只需要将所有边复原后，删除这条边（将它和它的反向边流量都置为 $0$ 即可），再重新跑一遍 $S$ 到 $T$ 的最小割用以得到新图的最小割即可。

最后将得到的”需破坏点“下标 $\text{sort}$ 一遍即可。

复杂度就是 $n$ 遍 $\text{dinic}$ 的复杂度，如果将边的数量看作 $n^2$ 的话，复杂度就是 $\Theta(n^5)$ 实际上哪里都不满

最后放一下代码

inline void add(rint x,rint y,rint flow)
{
	e[++cnt]=(Edge){y,head[x],flow},head[x]=cnt;
}

int bfs(rint s,rint t)
{
	memset(dis,0,sizeof(dis)),memcpy(tmphead,head,sizeof(head));
	queue<int> q;q.push(s),dis[s]=1;
	while(!q.empty())
	{
		rint u=q.front();q.pop();
		for(rint i=head[u];i;i=e[i].next)
		{
			rint v=e[i].to;
			if(!e[i].flow||dis[v]) continue;
			dis[v]=dis[u]+1,q.push(v);
			if(v==t) return 1;
		}
	}
	return 0;
}

int dfs(rint x,rint t,rint flow)
{
	if(x==t) return flow;
	rint rest=flow;
	for(rint i=tmphead[x];i;i=e[i].next)
	{
		tmphead[x]=i;rint v=e[i].to;
		if(!e[i].flow||dis[v]!=dis[x]+1) continue;
		rint tmp=dfs(v,t,min(rest,e[i].flow));
		tmp?e[i].flow-=tmp,e[i^1].flow+=tmp,rest-=tmp:dis[v]=0;
		if(!rest) return flow;
	}
	return flow-rest;
}

inline void add_edge(rint x,rint y,rint flow)
{
	add(x,y,flow),add(y,x,0);
}

int main()
{
	for(rint tt=read<int>();tt;tt--)
	{
		rint n=read<int>(),mx=0,s=0,t=n*2+1;memset(head,0,t+1<<2),cnt=1;
		for(rint i=1;i<=n;i++) a[i]=read<int>();
		for(rint i=1;i<=n;i++)
		{
			dp[i]=1;
			for(rint j=1;j<i;j++)
				if(a[i]>a[j])
					dp[i]=max(dp[i],dp[j]+1);
			mx=max(mx,dp[i]);
		}
		for(rint i=1;i<=n;i++) add_edge(i,i+n,read<int>());
		for(rint i=1;i<=n;i++)
		{
			if(dp[i]==1) add_edge(s,i,inf);
			if(dp[i]==mx) add_edge(i+n,t,inf);
			for(rint j=i+1;j<=n;j++)
				if(a[i]<a[j]&&dp[j]==dp[i]+1)
					add_edge(i+n,j,inf);
		}
		for(rint i=1;i<=n;i++) c[i]=(Node){read<int>(),i};
		sort(c+1,c+n+1,[](const Node &x,const Node &y){return x.val<y.val;});
		rll ans=0;rint N=0;
		while(bfs(s,t)) ans+=dfs(s,t,inf);
		for(rint i=1;i<=n;i++)
		{
			rint u=c[i].id,v=u+n;
			if(!bfs(u,v))
			{
				b[++N]=u,e[u*2].flow=e[u*2+1].flow=0;
				for(rint i=2;i<=cnt;i+=2) e[i].flow+=e[i^1].flow,e[i^1].flow=0;
				while(bfs(s,t)) dfs(s,t,inf);
			}
		}
		sort(b+1,b+N+1),printf("%lld %d\n",ans,N);
		for(rint i=1;i<=N;i++) printf("%d ",b[i]);puts("");
	}
	return 0;
}