over 2 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1050
分析:
首先我们肯定要按照边的大小排序,然后枚举哪一条边是当前的最小边,接着再确定最大边。
那么我们怎么求出这个最大边。。。暴力重建最小生成树是可以过的(虽然很慢),然而我们可以在中动态加边维护最大边,这样会快很多。
暴力重建树
动点spfa

← bzoj1049:[HAOI2006]数字序列 bzoj1051:[HAOI2006]受欢迎的牛 →
 
comments powered by Disqus