例题一

解题报告

解题思路

把题目阅览完之后，小伙伴们心中大抵知道这是最小生成树的题，因为题目信息给的很直接呀,hh，题目中让咱们求最小生成树的各边的长度之和。然后看给的数据范围，可以看出是稀疏图，那么Kruskal算法就可以拿出来了。 感觉起来，和咱们上面演示的例题是不是感觉换汤不换药呀。那就开始操作啦~

参考代码（C++版本）

例题二

解题报告

解题思路

题目要的是一棵方差最小的生成树

一、数学知识的回忆——方差

二、解决需求——计算方差

这道题要咱们求的方差最小，那么就是要求每条边的(权重 - 平均值)2的和最小。

因为随着每次输入是动态的，所以直接求平均值是比较困难的。这个时候，我们就可以拿出我们可爱的枚举。

我们可以枚举全部边权和的可能，对于每一个可能，都去执行Kruskal算法，执行的时候，把(权重 - 平均值)2作为真正要用的权重w。

同时，当我们先前枚举的边权和等于执行完Kruskal算法之后的生成树权值的和，此时就可以更新答案了。

参考代码(C++版本)

疑难杂症剖析

一、执行思路

执行的大框架仍然是可以套用kruskal算法的模板。

kruskal算法执行流程

二、圈定枚举的区间

    //minv就是可能出现的权值和的最小值，maxv则是可能出现的权值之和的最大值
        for(int i = 0; i < n - 1; i++)
            minv += tmp[i];
        for(int i = m - 1; i > m - n; i--)
            maxv += tmp[i];
        for(int i = minv; i <= maxv; i++)
            Kruskal(i);

因为最小生成树有n-1条边。

下界minv可以从存放在tmp数组（注：tmp数组已从小到大排序）中的权值依次获取n-1个最小值。

上界maxv则可以从存放在tmp数组的权值倒着获取n-1个最大值。

三、谨记需求

方差才是我们最后要获取的，所以在kruskal算法中进行排序前，把(权重 - 平均值)^2^作为真正要用的权重w。

    for(int i = 0; i < m; i++)
        e[i].w = (e[i].val - ave) * (e[i].val - ave);
  //重新排序
    sort(e, e + m, cmp);

例题三

例题描述：

解题报告

解题思路

一、第一感受

在阅览完例题之后，从"为了使花费最少，他希望用于连接所有的农场的光纤总长度尽可能短"这句话可以get到，这道题其实想让我们求这个图的最小生成树。\

二、看数据范围定算法

重新看看最小生成树问题中，在什么图中应该使用什么类型的算法模板

最小生成树算法大纲

对于这道题而言，从数据范围可以得知是稠密图，那么我们就可以回忆一下prim算法的实现流程然后去逐步落实。

参考代码(C++版本)

疑难杂症剖析

留意这道例题的输入输出，和我们上面用来演示的模板题又不太相似的喔 本题是一个输入，根据输入建立一个邻接矩阵，因此在代码落实到时候就更清爽了，初始化邻接矩阵和建图环节可以放在一起啦~

    //输入
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
        for(int j = 1;j<=n;j++) cin >>g[i][j];

总结

一、脑海中对稠密图和稀疏图应该使用的prim算法和kruskal算法的模板实现流程有个大致的印象，倘若忘了，可以回来看看实现流程和模板题喔

二、留意输入输出，从而对初始化和建图更清晰

三、最小生成树假如只是用来解决考试的话，只要明白通俗演示，然后可以画出各自的生成树就好。对于竞赛的同学就建议先熟悉模板，然后写题巩固，去亲自感受将图论问题中的图抽象出来的过程

四、图论问题难点主要是将问题中这个图抽象出来，然后才可以定，要用dfs解决？还是拓扑排序了？算法模板是可以很快的套上去的