---

分析题意可知,题目要求最小生成树,故采用kruskal算法。kruskal算法的关键是并查集的思想,find函数的作用是找父节点。首先我们利用排序将各边升序排,而后从小到大依次选边,如果find两个结点发现不连通,则使其连通(即使其有同一个父节点)。

具体代码如下：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 105;

struct node

{

  int u, v, w;

} edge[maxn * maxn];

int cmp(node a, node b)

{

  return a.w < b.w;

}

int fa[maxn];//记录每个结点的父节点

int find(int x)

{ // 本质是找父节点的操作

  if (x == fa[x])

    return x;

  fa[x] = find(fa[x]);//此条语句的作用是将图变为中心式,只有一个中心结点其他都是边结点，即只有一个父节点其他都是孩子

  return fa[x];

}

int main()

{

  int m, n;

  while (cin >> m >> n)

  {

    for (int i = 0; i < n; i++)

      cin >> edge[i].u >> edge[i].v >> edge[i].w;

    for (int i = 1; i <= m; i++)//将每个结点的父节点初始化为自己

      fa[i] = i;

    sort(edge, edge + n, cmp); // 贪心算法,每次选最短的那条边

    int w...