题解思路

问题分析

我们有一个特殊的图：每个点出度恰好为1。这种图称为功能性图，其结构特点是：

• 每个连通分量是一个基环树（一个环加上若干树）
• 每个环本身就是一个强连通分量
• 树上的点最终都指向环

关键观察

1. 强连通条件：整个图必须是一个单一的环
2. 当前状态：图由若干个环和树组成
3. 操作方式：可以改变任何点的出边目标，代价为 $C_i$

算法框架

步骤1：分析图结构

使用DFS或迭代找环算法，找出所有的环：

步骤2：分类讨论

情况1：整个图已经是一个环

• 花费 = 0（样例4）

情况2：图有多个连通分量（多个基环树）

• 需要合并所有分量形成一个大的环

步骤3：代价计算策略

对于每个基环树分量：

1. 环内代价：如果要打破这个环，需要修改环上的一条边

   • 选择环上 $C_i$ 最小的边进行修改

2. 树部分代价：对于指向环的树节点

   • 如果要改变指向，需要花费 $C_i$
   • 但我们可以选择保留某些指向

步骤4：全局最优策略

核心思想：保留一个环作为核心，其他所有分量都接入这个环

更精确的算法

1. 找环和树

使用DFS标记：

• 环上的节点
• 树上的节点（最终指向环）

2. 计算每个分量的"接入代价"

对于每个分量：

• 如果分量是一个环：接入代价 = 环上最小的 $C_i$

处理细节

环的检测技巧

由于每个点出度为1，可以用快慢指针：

代价优化

实际上，最优策略是：

1. 保留最大的环作为核心
2. 打破所有其他环：每个其他环花费其最小 $C_i$
3. 调整树结构：确保所有点最终指向核心环

完整算法流程

复杂度分析

• 找环：$O(N)$，每个点访问一次
• 计算最小代价：$O(N)$
• 总复杂度：$O(N)$

总结

这道题的关键在于理解功能性图的结构特性：

1. 识别基环树：每个连通分量是环+树
2. 强连通条件：整个图必须是一个环
3. 最优策略：保留一个环，打破其他环，让所有点最终接入这个环
4. 代价计算：打破每个环的代价是该环上最小的 $C_i$