自动搬运

查看原文

来自洛谷，原作者为

	SmokingTurtle https://www.luogu.me/paste/4mvfnsgj || 极少上线（家长原因） || ENTP || 一个可爱的ST表捏~ || 大号：shaozhehan

搬运于2025-08-24 23:10:43，当前版本为作者最后更新于2025-02-23 19:46:25，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

前置芝士

基环树和基环树森林

如果一张无向连通图包含恰好一个环，则称它是一棵基环树。

如果一张有向连通图每个点的入度都为 1，则称它是一棵基环外向树。

如果一张有向连通图每个点的出度都为 1，则称它是一棵基环内向树。

多棵基环树可以组成基环森林，多棵基环外向树可以组成基环外向树森林，多棵基环内向树可以组成基环内向森林。

——摘自 OIWIKI

基环树一般的处理办法转化为树上问题+环上问题。具体来说，一般会将环断开，变为若干棵树，每棵树单独计算，最后在环上统计答案。

tortoise-hare（乌龟-野兔）算法

见我的这篇专栏

题意概括

给定数列 $a_1,a_2,\cdots,a_n$，你可以修改其的若干项，使得对于任意 $i$，满足 $a_{a_i}=a_i$。修改第 $i$ 项的代价为 $c_i$。

题目分析

建模

我们发现题目中用到了 $a_{a_i}$ 甚至 $a_{a_{a_i}}$ 这种东西，导致下标可能会无限套下去，直接做显然十分困难。

考虑一个非常典的模型：将数列下标视为点，然后从 $i$ 到 $a_i$ 连一条有向边。

此时，由于有 $n$ 个点，每个点有且仅有一条出边（出度为 $1$），所以图构成了一个基环树森林。

显然，连通块之间互不影响，所以我们单独考虑每一个基环树。

我们发现，如果要修改 $a_i$，那么一定会将 $a_i$ 修改成 $i$。证明比较显然：

对于一种将 $a_i$ 修改为 $x\ \left(x\neq i\right)$ 的方案，我们知道此时不存在满足 $a_j=i$ 的 $j$（不然 $a_j=i\text{ 而 }a_{a_j}=x$）。既然如此，我们只需要考虑 $i$ 和 $a_i$ 的代价。

此时，如果 $a_i\neq i$，那么要求 $a_{a_i}=a_i$。然而，如果将 $a_i$ 改为 $i$，则不会增加代价，而且不会出现这条附加限制，所以肯定不劣。

接下来，我们考虑不修改的 $i$。对于这样的 $i$，要求 $a_{a_i}=a_{i}$。

于是，现在问题变成了：在基环树上选择若干个点，使得如果 $i$ 没有选择，那么 $i$ 的出边指向的节点必须选。

我们考虑转化为树上问题+环上问题（前文所说的套路）。

求解

找环

这里可以用前文所说的 tortoise-hare 算法。

树上部分

对于树上部分，他是一个比较典的树形 DP 题目。在没有上司的舞会这道题中将最大化收益改为最小化代价即可。具体的，令 $r_i$ （那道题中的快乐度）等于 $-c_i$（本题中的代价的相反数）即可。

大概思路是令 $dp_{i,0/1}$ 表示以 $i$ 为根的子树，$i$ 选/不选的代价。

转移方程：

$$dp_{i,0}=c_i+\sum\limits_{u\text{ 是 }i\text{ 的儿子}}\min(dp_{u,0},dp_{u,1}) $$$$dp_{i,1}=\sum\limits_{u\text{ 是 }i\text{ 的儿子}}dp_{u,0} $$

**upd 2025/03/23：第二个方程之前打错了，感谢

原因读者可以自行推导或者看上面提到的没有上司的舞会的题解，这里不再赘述。

环上问题

不妨设这个环上的所有点依次为 $ring_0,ring_1,\cdots,ring_{len-1}$。其中 ，$a_{ring_0}=ring_1,a_{ring_1}=ring_2,\cdots,a_{ring_{len-2}}=ring_{len-1},a_{ring_{len-1}}=ring_0$。

环上问题一般有三种解法：

1. 将环复制两遍，转化为在一个长度为 $2\times len$ 的序列上面寻找一个最优的长度为 $len$ 的区间。这个是最基础的，但是一般较慢（因为区间有 $O(n^2)$ 个）
2. 随意找一个地方将环断开，然后枚举最后一项和第一项之间的关系，转化为两个相似的序列问题。例题：P6064 Naptime。
3. 设每个点的答案分别为 $dp_1, dp_2,\cdots, dp_n$，求出相互之间关系，高斯消元求解。这种方法一般适用于期望 DP，较为复杂，超出了本题的讨论范围。

这里，我们肯定是选用第二种方法。具体的，设 $f_{i,0/1}$ 表示考虑 $ring_0,ring_1,\cdots ,ring_i$，其中 $ring_i$ 选/不选的答案。

那么转移方程和 $dp$ 数组类似：

$$f_{i,0}=dp_{ring_i,0}+\min(f_{i-1,0},f_{i-1,1})$$ $$f_{i,1}=dp_{ring_i,1}+f_{i-1,0}$$

其实维护两个变量即可，但是感觉这样稍微清晰一点。

那么初始值和最终答案是多少呢？那我们枚举 $ring_{len-1}\sim ring_0$ 的情况：

1. $ring_{len-1}$ 的 $a$ 值不修改：

此时，$ring_0$ 必须修改，所以 $f_{0,0}=dp_{ring_0,0},\ f_{0,1}=+\infin$。由于我们钦定 $ring_{len-1}$ 的 $a$ 不修改，所以最终答案为 $f_{len-1,1}$。

2. $ring_{len-1}$ 的 $a$ 值修改：

此时，$ring_0$ 可以修改也可以不修改，所以 $f_{0,0}=dp_{ring_0,0},\ f_{0,1}=dp_{ring_0,1}$。由于我们钦定 $ring_{len-1}$ 的 $a$ 修改，所以最终答案为 $f_{len-1,0}$。

因此，对于这两种情况，我们各自计算一次 $f$，然后将 $f_{len-1,1/0}$ 取一个 $\min$ 即可。

总结

现在，我们已经做完了这道题，再简要总结一下方法：

1. 首先，我们找到所有连通块。
2. 其次，对于每个连通块，我们找到环。
3. 然后，我们断开环上的边，对于环上每个点都作为根跑一遍树形 DP。
4. 接着，在环上再跑两次 DP 统计答案。
5. 最后，把所有连通块的答案全部加起来得到最终答案。

code

#include<iostream>
#include<vector>
using namespace std;
long long dp[200005][2],f[200005][2],c[200005];
bool done[200005],onring[200005];
vector<int> out[200005],ring;
const long long inf=4e18;
int in[200005];
void dfs(int u)//求 dp 数组的值
{
	done[u]=1;
	dp[u][0]=(u!=in[u])*c[u];
	for(int v:out[u])
		if(!onring[v] && !done[v])
			dfs(v),dp[u][0]+=min(dp[v][0],dp[v][1]),dp[u][1]+=dp[v][0];
}
long long deal(int x)//处理包含 x 的连通块的答案
{
	ring.clear();
	int y=x;
	do ring.push_back(y),onring[y]=1,y=in[y]; while(y!=x);//找环
	for(int u:ring)	dfs(u);//计算dp
	int len=ring.size();
	if(len==1)	return min(dp[ring[0]][0],dp[ring[0]][1]);
	for(int i=0;i<len;i++)	f[i][0]=f[i][1]=inf;
	f[0][0]=dp[ring[0]][0];
	for(int i=1;i<len;i++)
		f[i][0]=min(f[i][0],min(f[i-1][0],f[i-1][1])+dp[ring[i]][0]),
		f[i][1]=min(f[i][1],f[i-1][0]+dp[ring[i]][1]);
	long long ans=min(f[len-1][0],f[len-1][1]);

	for(int i=0;i<len;i++)	f[i][0]=f[i][1]=inf;
	f[0][0]=dp[ring[0]][0];
	f[0][1]=dp[ring[0]][1];
	for(int i=1;i<len;i++)
		f[i][0]=min(f[i][0],min(f[i-1][0],f[i-1][1])+dp[ring[i]][0]),
		f[i][1]=min(f[i][1],f[i-1][0]+dp[ring[i]][1]);
	ans=min(ans,f[len-1][0]);
	return ans;
}
int main()
{
	int n;
	cin>>n;
	long long ans=0;
	for(int i=1;i<=n;i++)	cin>>in[i],out[in[i]].push_back(i);
	for(int i=1;i<=n;i++)	cin>>c[i];
	for(int i=1;i<=n;i++)
		if(!done[i])//如果i所在连通块没有被遍历
		{
			int x=in[i],y=i;
			while(x!=y)	x=in[in[x]],y=in[y];//Floyd's Tortoise and Hare algorithm 算法
			long long tmp=deal(x);
			ans+=tmp;//最终对所有连通块求和
		}
	cout<<ans<<endl;
}