最小生成树（kruskal） hdu 1233

野性酷女 2022-08-27 10:46 191阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1233][http_acm.hdu.edu.cn_showproblem.php_pid_1233]

Problem Description

某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

Input

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

Output

对每个测试用例，在1行里输出最小的公路总长度。

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
    
    
       
        Hint Hint 
       
        
    Huge input, scanf is recommended.
      
       
      
       
    
      
       
      
       
    
      
       
      
       
    
      
       
      
       
        
       My opinion：标准的最小生成树，用并查集维护。
      
       
      
       
    
      
       
      
       
       
        #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <algorithm>
    using namespace std;
    
    struct E
    {
           int x,y,w;
           }e[5100];
    
    int i,k,fa[1002],n,A,B,p,m,ans;
    
    bool cmp(E p,E q)
    {
         return p.w<q.w;
         }
    
    int pre(int t)
    {
        if (fa[t]==t)
             return t;    
        return (fa[t]=pre(fa[t]));
    }
    
    int main()
    {
        while(scanf("%d", &n), n)
        {
              ans=0;
              m=n*(n-1)/2;
              for (i=1;i<=m;i++)
                 scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);
              sort(e+1,e+m+1,cmp);
              for (i=1;i<=n;i++)
                  fa[i]=i;
              for (i=1;i<=m;i++)
              {
                    A=pre(e[i].x);
                    B=pre(e[i].y);
                    if (A!=B)
                     {
                       fa[A]=B;
                       ans+=e[i].w;
                     }
              }
              printf("%d\n",ans);
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_1233]: http://acm.hdu.edu.cn/showproblem.php?pid=1233