首页 > 代码库 > hdu-1233 还是畅通工程

hdu-1233 还是畅通工程

2024-10-01 02:11:02   203人阅读

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1233

题目类型：

图论-最小生成树

题意概括:

计算将全省所有村庄都连接起来的最小公路长度

解题思路：

最小生成树模板

题目：

还是畅通工程

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


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.
 
# include <stdio.h># include <string.h># define M 105# define INF 99999999int map[M][M],lowcost[M];int prim(int v0,int n) {    int i,j;     bool vis[n];vis[v0]=true;     for(i=1 ;i<=n; i++)     {         if(i!=v0)         {             lowcost[i]=map[v0][i];             vis[i]=false;         }    }    int sum=0;        for(i=1; i<=n; i++)    {        int temp=INF;        int t=v0;        for(j=1;j<=n;j++)        {            if(!vis[j] && lowcost[j]<temp)            {                temp=lowcost[j];                t=j;            }                    }        if(t==v0)            return sum;        sum+=temp;        vis[t]=true;        for(j=1;j<=n;j++)            if(!vis[j] && lowcost[j]>map[t][j])                lowcost[j]=map[t][j];    }}int main (){    int n,a,b,c,i;    while(scanf("%d",&n),n)    {        memset(map,INF,sizeof(map));        for(i=1;i<=n*(n-1)/2;i++)        {            scanf("%d%d%d",&a,&b,&c);             map[a][b]=c;            map[b][a]=c;        }        printf("%d\n",prim(1,n));     }}

 

 

hdu-1233 还是畅通工程


联系
我们