BZOJ 1083 [SCOI2005] 繁忙的都市


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

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


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

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

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

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

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 1083 [SCOI2005] 繁忙的都市


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,