BZOJ 1083 [SCOI2005] 繁忙的都市

发布于 2017-06-22  124 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1083

题意:求一个图的某个生成树,满足最大边最小,输出最大边...


数据范围奇小无比... 只会乱♂搞,膜拜题解后得知这种生成树叫做瓶颈生成树.... 且

最小生成树一定是瓶颈生成树,但瓶颈生成树不一定是最小生成树

然后让我们尝试证 (口) 明 (胡) 一下第一句话,第二句话的错误性是显然的... 随便画画好了

反证:设最小生成树\(T\) 不是瓶颈生成树\(T_{lim}\),设\(T\) 中最大边权为\(e\),则必定满足\(T_{lim}\) 中边权均小于\(e\),删除这条边,则\(T\) 分裂成两个子树,用\(T_{lim}\) 中的边连接两个子树,得到的新树边权和一定小于\(T\),与假设矛盾,证毕...

 


一个非常弱的准退役OIER