首页 > 代码库 > 1813:还是畅通工程
1813:还是畅通工程
时间限制:1 秒
内存限制:32 兆
特殊判题: 否
提交:94
解决: 43
标签
- 最小生成树
题目描述
某省调查乡村交通状况,得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可),并要求铺设的公路总长度为最小。请计算最小的公路总长度。
输入格式
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 );随后的N(N-1)/2行对应村庄间的距离,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间的距离。为简单起见,村庄从1到N编号。
当N为0时,输入结束,该用例不被处理。
输出
对每个测试用例,在1行里输出最小的公路总长度。
样例输入
8
1 2 42
1 3 68
1 4 35
1 5 1
1 6 70
1 7 25
1 8 79
2 3 59
2 4 63
2 5 65
2 6 6
2 7 46
2 8 82
3 4 28
3 5 62
3 6 92
3 7 96
3 8 43
4 5 28
4 6 37
4 7 92
4 8 5
5 6 3
5 7 54
5 8 93
6 7 83
6 8 22
7 8 17
0
样例输出
82
稠密图,prim算法:
1 #include <stdio.h> 2 #define INF 500000 3 typedef struct 4 { 5 int eage[101][101]; 6 7 }GRAPH; 8 GRAPH g; 9 int main(Void)10 {11 //freopen("in.txt","r",stdin);12 int n;13 while(scanf("%d",&n)!=EOF&&n!=0)14 {15 int e;16 e=n*(n-1)/2;17 int i;18 int a,b,w;19 for(i=0;i<n;i++)20 {21 int j;22 for(j=1;j<=n;j++)23 g.eage[i][j]=INF;24 }25 for(i=1;i<=e;i++)26 {27 scanf("%d %d %d",&a,&b,&w); 28 g.eage[a][b]=w;29 g.eage[b][a]=w;30 31 }32 int lowcost[5000];33 int vset[5000];34 for(i=1;i<=n;i++)35 {36 lowcost[i]=g.eage[1][i];37 38 vset[i]=0;39 }40 vset[1]=1;41 int sum=0;42 int u;43 44 45 for(i=1;i<n;i++)//已经排除掉初始点,还剩下n-1次选择 46 { 47 int min=INF;48 int j;49 for(j=1;j<=n;j++)50 {51 if(vset[j]==0&&lowcost[j]<min)52 {53 min=lowcost[j];54 u=j;55 }56 57 }58 59 vset[u]=1;60 sum+=min;61 int k;62 for(k=1;k<=n;++k)63 {64 if(vset[k]==0&&g.eage[u][k]<lowcost[k])65 lowcost[k]=g.eage[u][k];66 }67 }68 printf("%d\n",sum);69 }70 return 0;71 72 }
Kruskal算法:
1 #include <stdio.h> 2 typedef struct 3 { 4 int a; 5 int b; 6 int w; 7 }ROAD; 8 ROAD road[5000]; 9 int v[5000];10 int getroot(int m)11 {12 13 while(m!=v[m])14 m=v[m];15 return m;16 }17 int main(void)18 {19 //freopen("in.txt","r",stdin);20 int n;21 int e;22 while(scanf("%d",&n)!=EOF&&n!=0)23 {24 int sum=0;25 e=n*(n-1)/2;26 int i;27 for(i=0;i<e;i++)28 {29 scanf("%d %d %d",&road[i].a,&road[i].b,&road[i].w);30 //printf("%d %d %d\n",road[i].a,road[i].b,road[i].w);31 }32 for(i=1;i<=n;i++)33 v[i]=i;34 for(i=e-1;i>0;i--)35 {36 int j;37 ROAD tmp;38 for(j=0;j<i;j++) 39 if(road[j].w>road[j+1].w)40 {41 tmp=road[j];42 road[j]=road[j+1];43 road[j+1]=tmp;44 45 }46 }47 for(i=0;i<e;i++)48 {49 int a,b;50 a=getroot(road[i].a);51 b=getroot(road[i].b);52 if(a!=b)53 {54 v[a]=b;55 sum+=road[i].w;56 }57 }58 printf("%d\n",sum);59 }60 return 0;61 }
prim耗时少很多
1813:还是畅通工程
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。