HDU1233（Kruskal&Prim两解）

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

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

Sample Output

3
5


        
 
Huge input, scanf is recommended.

//Kruskal

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<vector>
 7 #include<queue>
 8 const int maxn=105;
 9 #define ms(x,n) memset(x,n,sizeof x);
10 const int inf=0x3f3f3f3f;
11 using namespace std;
12 int n,m;
13 int u,v,w,parent[maxn];//ranks[maxn];
14 struct node
15 {
16     int u,v,w;
17     node(){u=0,v=0,w=inf;}
18     //node(int uu,int vv,int ww){u=uu,v=vv,w=ww;}
19 }edge[maxn*maxn];
20 bool cmp(node a,node b)
21 {
22     return a.w<b.w;
23 }
24 int init(int n)
25 {
26     for(int i=1;i<=n;i++)
27         parent[i]=-1;//,ranks[i]=-1;
28 }
29 int finds(int x)
30 {
31     if(parent[x]<0) return x;
32         return parent[x]=finds(parent[x]);
33 }
34 void unions(int x,int y)
35 {
36     x=finds(x),y=finds(y);
37     if(x==y) return;
38     if(parent[x]<parent[y])
39         {
40         parent[x]+=parent[y];
41         parent[y]=x;
42         }
43     else
44     {
45         parent[y]+=parent[x];
46         parent[x]=y;
47     }
48 }
49 int kruskal()
50 {
51     sort(edge+1,edge+m+1,cmp);
52     init(n);
53     int ans=0;
54     for(int i=1;i<=m;i++)
55     {
56         node a=edge[i];
57         if(finds(a.u)!=finds(a.v))
58         {
59             unions(a.u,a.v);
60             ans+=a.w;
61         }
62     }
63     return ans;
64 }
65 int main()
66 {
67     ios::sync_with_stdio(false);
68     cin.tie(0);
69     while(~scanf("%d",&n),n)
70     {
71         m=n*(n-1)/2;
72         for(int i=1;i<=m;i++)
73             edge[i]=node();
74         for(int i=1;i<=m;i++)
75         {
76             scanf("%d%d%d",&edge[i].u,&edge[i].v,&w);
77             edge[i].w=min(edge[i].w,w);
78         }
79         printf("%d
",kruskal());
80     }
81     return 0;
82 }

//Prim

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<vector>
 7 #include<queue>
 8 #define ms(x,n) memset(x,n,sizeof x);
 9 const int maxn=105;
10 const int inf=0x3f3f3f3f;
11 using namespace std;
12 int d[maxn],g[maxn][maxn];
13 int n;
14 bool vis[maxn];
15 void prim()
16 {
17     int i,j,k,tmp,ans=0;
18     ms(d,0x3f);
19     ms(vis,0);
20     d[1]=0;
21     for(i=1;i<=n;i++)
22     {
23         tmp=inf;
24         for(j=1;j<=n;j++)
25         {
26             if(!vis[j]&&tmp>d[j])
27             {
28                 tmp=d[j];
29                 k=j;
30             }
31         }
32         vis[k]=1;
33         ans+=tmp;
34         for(j=1;j<=n;j++)
35         {
36             if(!vis[j]&&d[j]>g[k][j])
37                 d[j]=g[k][j];
38         }
39     }
40     cout<<ans<<endl;
41 }
42 int main()
43 {
44     while(~scanf("%d",&n),n)
45     {
46         int m=n*(n-1)/2;
47         for(int i=1;i<=n;i++)
48             for(int j=1;j<=n;j++)
49             if(i!=j)
50             g[i][j]=inf;
51         else
52             g[i][j]=0;
53         for(int i=1;i<=m;i++)
54         {
55             int u,v,w;
56             scanf("%d%d%d",&u,&v,&w);
57             g[u][v]=g[v][u]=w;
58         }
59         prim();
60     }
61     return 0;
62 }