[POJ 3522] 求权和差最小的最小生成树

【题目大意】给定一个无向图,求它的一棵生成树,使得权最大的边的权和最小的边的权差值最小。

【算法分析】枚举最短的一条边,然后对权值大于它的边进行Kruskal。直到构建好最小生成树,看目前最大边和枚举的那条边的权值之差是否小于ans

【其它】本来1A的,居然因为G++编译器问题CE了一遍

【code】

#include

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注