首页 > ACM题库 > HDU-杭电 > HDU 1863 畅通工程-最小生成树-[解题报告] C++
2013
12-23

HDU 1863 畅通工程-最小生成树-[解题报告] C++

畅通工程

问题描述 :

省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可)。经过调查评估,得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序,计算出全省畅通需要的最低成本。

输入:

测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M ( < 100 );随后的 N
行对应村庄间道路的成本,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间道路的成本(也是正整数)。为简单起见,村庄从1到M编号。当N为0时,全部输入结束,相应的结果不要输出。

输出:

对每个测试用例,在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通,则输出“?”。

样例输入:

3 3
1 2 1
1 3 2
2 3 4
1 3
2 3 2
0 100

样例输出:

3
?

//裸的kruskal,如果不会的多看下并查集吧,不多说了
 #include<stdio.h>
 #include<string.h>
 #include<algorithm>
 using namespace std;
 #define maxn 100
 int fa[maxn],rank[maxn];
 struct node
 {
     int st,nd,ln;
 }edge[maxn*maxn];
 int cmp(node a,node b)
 {
     return a.ln<b.ln;
 }
 void init()
 {
     int i;
     for(i=0;i<maxn;i++)
     {
         rank[i]=1;
         fa[i]=i;
     }
 }
 int findfather(int x)
 {
     if(x!=fa[x])
         fa[x]=findfather(fa[x]);
     return fa[x];
 }
 void kruskal(int n,int m)
 {
     int ans,num,i,x,y;
     ans=num=0;
     sort(edge+1,edge+1+n,cmp);
     for(i=1;i<=n;i++)
     {
         x=findfather(edge[i].st);
         y=findfather(edge[i].nd);
         if(x!=y)
         {
             ans+=edge[i].ln;
             if(rank[x]>rank[y])
             {
                 fa[y]=x;
                 rank[x]+=rank[y];
             }
             else
             {
                 fa[x]=y;
                 rank[y]+=rank[x];
             }
             if(++num==m-1)
                 break;
         }
     }
     if(num==m-1)
         printf("%d\n",ans);
     else
         printf("?\n");
 }
 int main()
 {
     int n,m,i;
     while(scanf("%d",&n)!=EOF)
     {
         init();
         scanf("%d",&m);
         if(n==0)
             break;
         for(i=1;i<=n;i++)
         {
             scanf("%d%d%d",&edge[i].st,&edge[i].nd,&edge[i].ln);
         }
         if(n<m-1)
         {
             printf("?\n");
             continue;
         }
         kruskal(n,m);
     }
     return 0;
 }

 

解题报告转自:http://www.cnblogs.com/M-cag/archive/2012/08/08/2628684.html