C++算法题,图论问题,给定N个顶点及M条边,求能使所有顶点连通,且最大边与最小边之差最小
问题描述：
C++算法题,图论问题,给定N个顶点及M条边,求能使所有顶点连通,且最大边与最小边之差最小
也就是这个
xxx国“山头乡”有n个村子,*准备修建乡村公路,由于地形复杂,有些乡村之间可能无法修筑公路,因此*经过仔细的考察,终于得到了所有可能的修路费用数据.并将其公布于众,广泛征求村民的修路意见.嗯,xxx国真是一个平等的国度.
*考虑到费用问题,因此要求只能建n-1条公路,而且这n-1条公路还能连通n个村子,而且调查数据表明,这完全是可行的.
村民们展开了激烈的讨论,最后大家达成一致,要求每条路的费用要尽可能一样,这是基于“平等”的考虑,汗~
xxx国*头脑简单,这这,太难了,最后双方又达成一致,那就保证费用最大的那条与费用最小的那条之间的费用之差尽可能最小吧.
现在的问题就交给你了,要你找出满足以上条件的一种方案,你只要输出费用最大的那条公路与费用最小的那条公路之间费用的差值w即可.嗯,因为这个数据还得告知村民,还是要“平等”.
答
其实是叫你求一个生成树,使得这个生成树中最大边和最小边的差值尽可能小.
算法只需要改变一下一般的最小生成树算法就行,kruscal原本是取最小边开始构建生成树,现在需要逐个枚举最小的边来构建一堆生成树,找出最优的那种.
也许你可以参考这个文章: