自动搬运

查看原文

来自洛谷，原作者为

	mxjz666 114514

搬运于2025-08-24 23:02:39，当前版本为作者最后更新于2024-11-27 17:27:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路

本题如果将 $i$ 向 $a_i$ 连边，那么就成了基环树内向树森林，不好处理，所以我们将 $a_i$ 向 $i$ 连边，这样就成了基环树外向树森林。

考虑某一棵基环树： 先找到环上的一点 $p$ 断掉 $p$ 与 $a_p$ 的连边，这样就成了一棵以 $p$ 为根的树。 接着设 $f_{x,0/1}$ 表示 $x$ 不选/选时，以 $x$ 为根的子树的最多可以投放的个数。 状态转移方程为 $f_{x,0}=\sum\limits_{y \in Son(x)} \max(f_{y,0},f_{y,1})$

$f_{x,1}=1+\max\limits_{y \in Son(x)}\{f_{y,0}+\sum\limits_{z \in Son(x),z\neq y} \max(f_{z,0},f_{z,1})\}$

但其中 $f_{x,1}$ 的转移是可以优化的，进而优化成：

$f_{x,1}=1+f_{x,0}-\min\limits_{y \in Son(x)}\{\max(f_{y,0},f_{y,1})-f_{y,0}\}$

然后，因为这是忽略了 $p$ 可以限制 $a_p$ 这个条件，所以这是我们可以让 $p$ 强制限制 $a_p$ 这样再计算一次。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int bid,h[N],nxt[N],to[N],n,a[N],f[N][2],ans,km;
bool vis[N];
void add(int x,int y){
	to[++bid]=y;
	nxt[bid]=h[x];
	h[x]=bid;
}
int dp(int x,int d){
	f[x][0]=f[x][1]=0;
	vis[x]=1;
	int res=0,c=1e9+7;
	for(int i=h[x];i;i=nxt[i]){
		int y=to[i];
		if(y==km)continue;
		res=dp(y,d);
		c=min(c,res-f[y][0]);
		f[x][0]+=res;
	}
	f[x][1]=f[x][0]-c+1;
	if(d&&x==a[km])f[x][1]+=c;
	return max(f[x][0],f[x][1]);
}
int hjw(int x){
	for(km=x;!vis[a[km]];vis[km]=1)km=a[km];
	int cnt=dp(km,0);
	dp(km,1);
	return max(cnt,f[km][0]);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		add(a[i],i);
	}
	for(int i=1;i<=n;i++)if(!vis[i])ans+=hjw(i);
	cout<<ans;
	return 0;
}