HDOJ---1233 还是畅通工程[Prim算法||Kruskal算法]

布满荆棘的人生 2022-04-10 14:11 159阅读 0赞

# 还是畅通工程 #

**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年 ][-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 }

[-2006_]: http://acm.hdu.edu.cn/search.php?field=problem&key=%E6%B5%99%E5%A4%A7%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A0%94%E7%A9%B6%E7%94%9F%E5%A4%8D%E8%AF%95%E4%B8%8A%E6%9C%BA%E8%80%83%E8%AF%95-2006%E5%B9%B4&source=1&searchmode=source