题目大意：给出n个点的坐标(x,y)，要求用线段将n个点连接起来，求最小的线段和。
最小生成树问题，用Kruskal算法进行求解，其中用到了并查集。将所有的点连接，构成一张图，对每一条边进行编号，两点间的距离作为权重。
1 #include2 #include 3 #include 4 #define square(x) (x)*(x) 5 #define MAXN 10000 6 #define POINTN 100+10 7 using namespace std; 8 9 double w[MAXN], point[POINTN][2]; // the weight of edge10 int u[MAXN], v[MAXN], r[MAXN], p[MAXN]; 11 // u[i] and v[i] save the end points of the ith edge seperately, r[i] save the ith edge of non-decreasing ordered edges12 13 double distance(double x1, double y1, double x2, double y2)14 {15 double t = square(x2-x1) + square(y2-y1);16 return sqrt(t);17 }18 19 int cmp(const int i, const int j)20 {21 return w[i] < w[j];22 }23 24 int find(int x)25 {26 return p[x] == x ? x : p[x] = find(p[x]);27 }28 29 int main()30 {31 #ifdef LOCAL32 freopen("in", "r", stdin);33 #endif34 int N;35 scanf("%d", &N);36 bool first = true;37 while (N--)38 {39 int n;40 scanf("%d", &n);41 for (int i = 0; i < n; i++)42 scanf("%lf%lf", &point[i][0], &point[i][1]);43 int k = 0; // the size of edge44 for (int i = 0; i < n; i++)45 for (int j = i+1; j < n; j++)46 {47 w[k] = distance(point[i][0], point[i][1], point[j][0], point[j][1]);48 u[k] = i;49 v[k] = j;50 k++;51 }52 double ans = 0;53 for (int i = 0; i < n; i++) p[i] = i;54 for (int i = 0; i < k; i++) r[i] = i;55 sort(r, r+k, cmp); // sort the edge56 for (int i = 0; i < k; i++)57 {58 int e = r[i];59 int x = find(u[e]);60 int y = find(v[e]);61 if (x != y)62 {63 ans += w[e];64 p[x] = y;65 }66 }67 if (first) first = false;68 else printf("\n");69 printf("%.2lf\n", ans);70 }71 return 0;72 }
代码中用到了间接排序——排序的关键字是对象的“代号”，而不是对象本身，将排序后第i小的边的序号保存在r[i]中。这样对象本身的数据就不需要移动了，比如这道题的u[i]和v[i]，自己也就能理解到这点了...代码是照抄别人的，解释还是照抄别人的...人工版的Ctrl-C & Ctrl-V 啊...