#include 
     
      #include 
      
       #include 
       
        #include 
        
         //bool cmp()int next[5000];int f[5000], t[5000];int r[5000], w[5000];int cmp(const void *p1, const void *p2){    return w[*(int*)p1] - w[*(int*)p2];}int find(int x){    return x == next[x] ? x : find(next[x]);}void findnext(int i, int j){    int x = find(i);    int y = find(j);    if (x != y)    {        if (x > y)        {            next[x] = y;        }        else next[y] = x;    }}int kruskal(int m, int n){    int res = 0;    for (int i=1; i<=n; i++)    {        next[i] = i;    }    for (int i=1; i<=m; i++)    {        r[i] = i;    }    qsort(r, m, sizeof(r[0]), cmp);    for (int i=1; i<=m; i++)    {       int e = r[i];       int x = find(f[e]);       int y = find(t[e]);       if (x != y)       {           res += w[e];           findnext(x, y);       }    }    return res;}int main(void){    int n;    while (scanf("%d", &n), n)    {        int m = n * (n-1) / 2;        for (int i=1; i<=m; i++)        {            scanf("%d%d%d", &f[i], &t[i], &w[i]);        }        printf("%d\n", kruskal(m, n));    }    return 0;}
        
       
      
     

 

Description

既然大家都不愿意做水题，元帅也很无奈，想了好久也不知道什么是水题，因为在元帅的眼里都是水题，他定义的非水题就是他做不出来的题。太囧了，随便弄个水的MST。

Input

测试输入包含若干测试用例。每个测试用例的第1行给出顶点数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个顶点的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。

当N为0时，输入结束，该用例不被处理。

Output

对于每个测试用例，输出MST的最小路径总长度。

Sample Input

3

1 2 1

1 3 2

2 3 4

4

1 2 1

1 3 4

1 4 1

2 3 3

2 4 2

3 4 5

0

Sample Output

3

5