这题，典型的最小生成树问题，可以用Kruskal算法来实现，配合着并查集来高效求解。
先将各边按权值进行从小到大排列。遍历一个各边便可求解，时间复杂度为O（|E|log|V|），其中E为边的个数，V为顶点数。
下面是AC代码，代码中有注释：
#include <iostream>#include <cstdio>#include <algorithm>using namespace std;class data{public:int from, to, cost; //起点、终点、权值};data con[5000];//定义边的结构体数组int n, m, par[105];int finds(int x)//并查集查找函数。{if(x == par[x])return x;elsereturn par[x] = finds(par[x]);}void unite(int x, int y) //并查集合并函数{x = finds(x);y = finds(y);if(x == y)return;if(x < y)par[y] = x;elsepar[x] = y;}int cmp(const data& a, const data& b) //排序的方式{return a.cost < b.cost;}int Kru(){int ans = 0;for(int i = 0; i <= n; i++)//初始化并查集par[i] = i;sort(con, con + m, cmp);//排序for(int j = 0; j < m; j++){if(finds(con[j].from) != finds(con[j].to)) //判断是否属于同一个并查集，不是，，则可以进行合并，这样就不会产生圈{unite(con[j].from, con[j].to);//进行合并ans += con[j].cost;//加上权值}}return ans;}int main(){// freopen("data.txt", "r", stdin);while(scanf("%d", &n) != EOF && n){m = n * (n – 1) / 2;for(int i = 0; i < m; i++){scanf("%d%d%d", &con[i].from, &con[i].to, &con[i].cost);}int ans = Kru();cout << ans << endl;}return 0;}
家门前的那条小路，到底通向了什么样的远方呢？
