CodeforcesLuogu分析显然先把最小割树建出来。首先有一个结论：第一问答案的上界为最小割树上所有边权之和。下面考虑怎样达到这个上界。考虑最小割树上的最小边，我们应让它只被经过一次。设它的两个端点为 $a_i,a_{i+1}$ ，则 $a_{1..i-1}$ 中任意两点不经过该边，$a_{i+2..n}$ 中任意两点不经过该边。于是将该边断掉后两边递归处理即可。代码// ======...
LuoguLOJ分析首先建出最小割树。因为两点间的最小割就是在最小割树路径上边权的最小值，分析一下可以得到答案就是最小割树上不同的边权数。于是直接拿一个 set 维护一下所有边权即可。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =====...
Luogu分析最小割树模板题。建出最小割树，查询直接暴力枚举点对就好了。可以在建完最小割树后暴力算出所有点对的最小割。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #i...