题目大意：给出n个点的坐标(x,y)，要求用线段将n个点连接起来，求最小的线段和。
最小生成树问题，用Kruskal算法进行求解，其中用到了并查集。将所有的点连接，构成一张图，对每一条边进行编号，两点间的距离作为权重。
#include <cstdio>
#include <algorithm>
#include <cmath>
#define square(x) (x)*(x)
#define MAXN 10000
#define POINTN 100+10
using namespace std; double w[MAXN], point[POINTN][]; // the weight of edge
int u[MAXN], v[MAXN], r[MAXN], p[MAXN];
// u[i] and v[i] save the end points of the ith edge seperately, r[i] save the ith edge of non-decreasing ordered edges double distance(double x1, double y1, double x2, double y2)
{
double t = square(x2-x1) + square(y2-y1);
return sqrt(t);
} int cmp(const int i, const int j)
{
return w[i] < w[j];
} int find(int x)
{
return p[x] == x ? x : p[x] = find(p[x]);
} int main()
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
int N;
scanf("%d", &N);
bool first = true;
while (N--)
{
int n;
scanf("%d", &n);
for (int i = ; i < n; i++)
scanf("%lf%lf", &point[i][], &point[i][]);
int k = ; // the size of edge
for (int i = ; i < n; i++)
for (int j = i+; j < n; j++)
{
w[k] = distance(point[i][], point[i][], point[j][], point[j][]);
u[k] = i;
v[k] = j;
k++;
}
double ans = ;
for (int i = ; i < n; i++) p[i] = i;
for (int i = ; i < k; i++) r[i] = i;
sort(r, r+k, cmp); // sort the edge
for (int i = ; i < k; i++)
{
int e = r[i];
int x = find(u[e]);
int y = find(v[e]);
if (x != y)
{
ans += w[e];
p[x] = y;
}
}
if (first) first = false;
else printf("\n");
printf("%.2lf\n", ans);
}
return ;
}
代码中用到了间接排序——排序的关键字是对象的“代号”，而不是对象本身，将排序后第i小的边的序号保存在r[i]中。这样对象本身的数据就不需要移动了，比如这道题的u[i]和v[i]，自己也就能理解到这点了...代码是照抄别人的，解释还是照抄别人的...人工版的Ctrl-C & Ctrl-V 啊...