题解 P2330 【[SCOI2005]繁忙的都市】

Created_equal1 · 2015-10-22 21:46:53 · 题解

算法1：

题面中有最大值最小，典型的二分！首先二分边权，然后把边权小于等于二分的边权的边全部用并查集连接到一起，判断是否联通即可。

算法2：

本题要求求的就是瓶颈MST，即最大边权最小的生成树。有个定理：一棵最小生成树必定是一棵最小瓶颈生成树。所以我们直接做一遍最小生成树即可