题解 | #还是畅通工程#

#include <stdio.h>
//思路 并查集 同175连通图，只不过多了一个存放被选中边的暂时数组，以备最后求边的权值之和时候使用
//注意：在遍历合适的边的时候，直接对所有边进行遍历，不要设置提前终止条件，暴力遍历完即可
int father [100];
int Find(int x) { //找祖先
  if (father[x] == x) {
    return father[x];
  } else {
    father[x] = Find(father[x]);
    return father[x];
  }
}
typedef struct edge {
  int x;
  int y;
  int length;
} enode;
int main() {
  int n;
  while (scanf("%d", &n) != EOF) {

    enode e[n * (n - 1) / 2];
    for (int i = 1; i <= n; i++) {
      father[i] = i;

    }
    for (int i = 0; i < n * (n - 1) / 2; i++) {
      scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].length);
    }
    enode temp;
    for (int i = 0; i < n * (n - 1) / 2 - 1; i++) { //排序 小的最前
      for (int j = n * (n - 1) / 2 - 1; j > i; j--) {
        if (e[j].length < e[j - 1].length) {
          temp = e[j - 1];
          e[j - 1] = e[j];
          e[j] = temp;
        }
      }
    }
    enode s2[n * (n - 1) / 2];
    int flag = 0;
    int edgnum = 0;
    for (int i = 0; i < n * (n - 1) / 2 - 1; i++) {
      int x = Find(e[i].x);
      int y = Find(e[i].y);

      if (Find(e[i].x) != Find(e[i].y)) {
        s2[edgnum] = e[i];
        edgnum++;
        father[Find(e[i].y)] = father[Find(e[i].x)];
      }
    }
    int sum = 0;
    for (int i = 0; i < edgnum; i++) {
      sum = sum + s2[i].length;
    }
    printf("%d\n", sum);



  }

}