P11842 [USACO25FEB] Bessie's Function G

· · 题解

前置芝士

基环树和基环树森林

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

如果一张有向连通图每个点的入度都为 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：第二个方程之前打错了，感谢 @lcy6

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

环上问题

不妨设这个环上的所有点依次为 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_0$ 必须修改，所以 $f_{0,0}=dp_{ring_0,0},\ f_{0,1}=+\infin$。由于我们钦定 $ring_{len-1}$ 的 $a$ 不修改，所以最终答案为 $f_{len-1,1}$。
  2. > 此时，$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;
}