类似于Kruskal算法,所有边从小到大排序,枚举每一条边建公路,直到所有的点都能连通为止(用并查集判断)
然后我去网上查了一下别人的代码,我查到的所有人都说是求最小生成树的最长边的权值,但是如果真的是这样,那这一组数据他绝对是过不了的。140 2 3 21 0 2 33 2 0 22 3 2 0但是,我把他们的代码复制下来,然后用这组数据试了一下,发现居然都能得出正确答案,也不知道他们代码都是怎么写的。现在举例说明:最小生成树的最长边权值并不等价于使图连通的所有边的最长边的可能取到的最小值。如本图所示,即上组测试数据的图,显然,最小生成树的所有边的和应该是7,此时最长边应该是3,但是,但是,但是,四条权值为2的边就可以使图连通,最长边的可能取到的最小值为2!备注:代码完全手打,一次ac,并查集魔板(魔法的魔)回来一定要好好整理一个。
新闻热点
疑难解答