这一题，就是简单的最小生成树的应用。开始，没有想到用最小生成树做，想到的是贪心，当知道了用最小生成树做的时候，，还犯了一个很严重的错误，就是时间复杂度的估计错了，导致开始不敢写，在想其他的办法。当作一次教训吧。
下面是AC的代码，有详细的注释，用的是并查集来判环，时间复杂度为nlogn，主要时间在排序上。
#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>using namespace std;class data//每两个点直接的边的数据{public:int from, to;//起点与终点double dis;//距离};data Dis[15000];//最多边的时候，大概接近10000double xy[105][2];int par[105], n, m;//par为并查集int cmp(const data& a, const data& b) //排序按距离从小到大排{return a.dis < b.dis;}int finds(int x)//并查集查找函数{if(x == par[x])return x;elsereturn par[x] = finds(par[x]);}void join(int x, int y)//并查集合并函数{x = finds(x);y = finds(y);if(x != y)par[y] = x;}double kru()//kruskal算法{for(int i = 0; i <= n; i++) //初始化并查集{par[i] = i;}sort(Dis, Dis + m, cmp);//排序double ans = 0.0;for(int j = 0; j < m; j++){if(finds(Dis[j].from) != finds(Dis[j].to)) //判是否存在环{ans += Dis[j].dis;join(Dis[j].from, Dis[j].to);//合并两点}}return ans;}int main(){while(scanf("%d", &n) != EOF){m = 0;for(int i = 0; i < n; i++){scanf("%lf%lf", &xy[i][0], &xy[i][1]);}for(int j = 0; j < n; j++)//求每两点之间的距离{for(int k = j + 1; k < n; k++){Dis[m].from = j;Dis[m].to = k;Dis[m++].dis = sqrt(pow((xy[j][0] – xy[k][0]), 2) + pow((xy[j][1] – xy[k][1]), 2));}}double ans = kru();printf("%.2lf\n", ans);//这里用C++提交的，如果用G++，应该改成 %.2f}return 0;}
来说是非者，便是是非人。
