一座 n 个点的基环外向树森林, 改变第 i 个点的入边, 代价为 ci. 求变成一个环的最小代价. (2 ≤ n ≤ 10^5, 1 ≤ ci ≤ 10^9) 考虑保留哪些边. 除非原来就是一个环 (特判这种情况), 保留的一定是一条条顶点不相交的链. 把 ci 看作入边的边权.
转化: 选出一些顶点不相交的链, 使权值之和最大.
每棵基环树是独立的.
如果是树, 显然可以贪心: 对于每个点, 把它的入边中边权最大者加入答案.
现在是基环树. 不妨先无视掉那条返祖边. 只要不是整个环都被选中, 就是合法的. 否则, 只需要用一条树边替换环上的边. 对于环上所有点, 求出 max { 出边边权的次大值 - 出边边权的最大值 } 即可.
一遍 DFS 即可.
有这个转化, 题目就变得简单了......但是我的思路不太对, 总觉得这个问题和最小生成树有关......最终成功把本题它归约到旅行商问题......这样并没有利用基环树森林这个条件啊.