HDOJ1233 还是畅通工程[Prim算法||Kruskal算法]

还是畅通工程

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 14115 Accepted Submission(s): 6435

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.

Source

浙大计算机研究生复试上机考试-2006年

Recommend

JGShining

Kruskal算法

code:

 1 #include <iostream>   
 2 #include <iomanip>   
 3 #include <fstream>   
 4 #include <sstream>   
 5 #include <algorithm>   
 6 #include <string>   
 7 #include <set>   
 8 #include <utility>   
 9 #include <queue>   
10 #include <stack>   
11 #include <list>   
12 #include <vector>   
13 #include <cstdio>   
14 #include <cstdlib>   
15 #include <cstring>   
16 #include <cmath>   
17 #include <ctime>   
18 #include <ctype.h> 
19 using namespace std;
20 
21 #define MAXN 101
22 
23 int father[MAXN];   
24 int n;
25 int cnt;           //已经选取的点的个数
26 int sum;           //路径的长度
27 
28 typedef struct edge
29 {
30     int x,y;
31     int len;
32 }Edge;
33 
34 Edge edge[MAXN*MAXN]; 
35 
36 int cmp(const Edge &a,const Edge &b)
37 {
38     return a.len<b.len;
39 }
40 
41 int findset(int v)
42 {
43     return father[v];
44 }
45 
46 void merget(int a,int b)
47 {
48     int i;
49     for(i=1;i<=n;i++)
50         if(father[i]==a)
51             father[i]=b;
52 }
53 
54 int main()
55 {
56     int i;
57     int m;
58     int tempx,tempy;
59     while(~scanf("%d",&n),n)                 //n为村庄个数
60     {
61         cnt=0;
62         sum=0;
63         m=((n-1)*n)>>1;                      //最多m条边
64         memset(edge,0,sizeof(edge));
65         for(i=1;i<=n;i++)
66             father[i]=i;
67         for(i=0;i<m;i++)
68             scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].len);
69         sort(edge,edge+i,cmp);                //对边进行排序
70         for(i=0;i<m&&cnt!=n;i++)
71         {
72             tempx=findset(edge[i].x);
73             tempy=findset(edge[i].y);
74             if(tempx!=tempy)
75             {
76                 merget(tempx,tempy);
77                 cnt++;
78                 sum+=edge[i].len;
79             }
80         }
81         printf("%d\n",sum);
82     }
83     return 0;
84 }

Prim算法：

code:

 1 #include <iostream>   
 2 #include <iomanip>   
 3 #include <fstream>   
 4 #include <sstream>   
 5 #include <algorithm>   
 6 #include <string>   
 7 #include <set>   
 8 #include <utility>   
 9 #include <queue>   
10 #include <stack>   
11 #include <list>   
12 #include <vector>   
13 #include <cstdio>   
14 #include <cstdlib>   
15 #include <cstring>   
16 #include <cmath>   
17 #include <ctime>   
18 #include <ctype.h> 
19 using namespace std;
20 
21 #define MAXN 101
22 
23 int map[MAXN][MAXN];
24 int vst[MAXN];
25 int dis[MAXN];
26 int n;
27 
28 int prim()
29 {
30     
31     int i,j,k;
32     int min,sum=0;
33     memset(vst,0,sizeof(vst));
34     for(i=1;i<=n;i++)           
35         dis[i]=map[1][i];
36     vst[1]=1;
37     for(i=2;i<=n;i++)
38     {
39         k=1;
40         min=INT_MAX;
41         for(j=2;j<=n;j++)
42             if(dis[j]<min&&!vst[j])               
43             {
44                 min=dis[j];
45                 k=j;
46             }
47         sum+=min;
48         vst[k]=1;
49         for(j=1;j<=n;j++)
50             if(map[k][j]<dis[j])
51                 dis[j]=map[k][j];
52     }
53     return sum;
54 }
55 
56 int main()
57 {
58     int i,j;
59     int m;
60     int tempx,tempy,templen;
61     int cost;
62     while(~scanf("%d",&n),n)
63     {
64         m=(n*(n-1))>>1;
65         for(i=1;i<=m;i++)
66         {
67             scanf("%d%d%d",&tempx,&tempy,&templen);
68             map[tempx][tempy]=templen;
69             map[tempy][tempx]=templen;
70         }
71         printf("%d\n",prim());
72     }
73     return 0;
74 }