首先我们需要什么是最小生成树
举个例子：
假如有10个村庄，你需要走遍这10个村庄，不漏掉任何一个村庄，如何走最省力（路程最短），就是最小生成树了。
Description
既然大家都不愿意做水题，元帅也很无奈，想了好久也不知道什么是水题，因为在元帅的眼里都是水题，他定义的非水题就是他做不出来的题。太囧了，随便弄个水的MST。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出顶点数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个顶点的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。
Output
对于每个测试用例，输出MST的最小路径总长度。
Sample Input
3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0
Sample Output
3
5
参考代码（Kruskal算法）
#include <cstdio>
#include <algorithm>
#include <cstring>
struct node
{int u, v, w;
}edge[1000*1000];
int fs[1001];
int n, m;
int cmp(node a,node b)
{return a.w < b.w;
}
int find(int x)
{if (fs[x] == x)return x;elsereturn fs[x] = find(fs[x]);
}
void init()
{for (int i = 1;i <= n;i++)fs[i] = i;
}
bool same(int a, int b)
{if (find(a) == find(b))return true;elsereturn false;
}
void mix(int a,int b)
{int t1 = find(a);int t2 = find(b);if (t1 != t2)fs[t2] = t1;
}
int Kruskal()
{int res = 0;for (int i = 1;i <= m;i++){if (same(edge[i].u, edge[i].v))continue;mix(edge[i].u, edge[i].v);res += edge[i].w;}return res;
}
int main()
{while (~scanf("%d", &n) && n){init();m = n*(n - 1) / 2;for (int i = 1;i <= m;i++)scanf("%d %d %d", &edge[i].u, &edge[i].v, &edge[i].w);std::sort(edge + 1, edge + m + 1, cmp);printf("%d\n",Kruskal());}
}参考代码（Prim算法|有BUG，仅供参考）
#include <cstdio>
#include <cstring>
#define INF 0x3f3f3f
int mp[1005][1005];
int dis[1005];
int lowcost[1005];
int mst[1005];
int n, m;
int prim(int graph[][1005], int n)
{int i, j, min, minid, sum = 0;for (i = 2; i <= n; i++){lowcost[i] = graph[1][i];mst[i] = 1;}mst[1] = 0;for (i = 2; i <= n; i++){min = INF;minid = 0;for (j = 2; j <= n; j++){if (lowcost[j] < min && lowcost[j] != 0){min = lowcost[j];minid = j;}}sum += min;lowcost[minid] = 0;for (j = 2; j <= n; j++){if (graph[minid][j] < lowcost[j]){lowcost[j] = graph[minid][j];mst[j] = minid;}}}return sum;
}
int main()
{while (~scanf("%d", &n) && n){for (int i = 1;i <= n;i++){for (int j = 1;j <= n;j++){mp[i][j] = INF;}}m = n*(n - 1) / 2;for (int i = 1;i <=m ;i++){int st, ed, value;scanf("%d %d %d", &st, &ed, &value);mp[st][ed] = mp[ed][st]=value;}printf("%d\n", prim(mp,n));}
}参考视频
https://www.bilibili.com/video/av4768483/?from=search&seid=17111035215682928699