CF343E Pumping Stations
Codeforces Luogu 分析 显然先把最小割树建出来。 首先有一个结论：第一问答案的上界为最小割树上所有边权之和。 下面考虑怎样达到这个上界。 考虑最小割树上的最小边，我们应让它只被经过一次。设它的两个端点为 $a_i,a_{i+1}$ ，则 $a_{1..i-1}$ 中任意两点不经过该边，$a_{i+2..n}$ 中任意两点不经过该边。于是将该边断掉后两边递归处理即可。 代码 /...
Codeforces Luogu 分析 显然先把最小割树建出来。 首先有一个结论：第一问答案的上界为最小割树上所有边权之和。 下面考虑怎样达到这个上界。 考虑最小割树上的最小边，我们应让它只被经过一次。设它的两个端点为 $a_i,a_{i+1}$ ，则 $a_{1..i-1}$ 中任意两点不经过该边，$a_{i+2..n}$ 中任意两点不经过该边。于是将该边断掉后两边递归处理即可。 代码 /...