時間限制: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