时间限制: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
样例输出
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耗时少很多
转载于:https://www.cnblogs.com/sairre/p/3958610.html