生活随笔
收集整理的這篇文章主要介紹了
08-图7 公路村村通 (30分)
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
是關于最小生成樹的問題(包含v個頂點v-1條邊，且邊的權重和最小)，利用Kruskal貪心算法–將邊合并成樹，每次都取權值最小的邊并且不構成回路，就利用到了并查集的算法（用數(shù)組存父節(jié)點）。
08-圖7 公路村村通 (30分)
現(xiàn)有村落間道路的統(tǒng)計數(shù)據(jù)表中，列出了有可能建設成標準公路的若干條道路的成本，求使每個村落都有公路連通所需要的最低成本。
輸入格式:
輸入數(shù)據(jù)包括城鎮(zhèn)數(shù)目正整數(shù)N（≤1000）和候選道路數(shù)目M（≤3N）；隨后的M行對應M條道路，每行給出3個正整數(shù)，分別是該條道路直接連通的兩個城鎮(zhèn)的編號以及該道路改建的預算成本。為簡單起見，城鎮(zhèn)從1到N編號。
輸出格式:
輸出村村通需要的最低成本。如果輸入數(shù)據(jù)不足以保證暢通，則輸出?1，表示需要建設更多公路。
#include
<stdio
.h
>
#define Max
1000
typedef struct
{int x
,y
;int cost
;
}box
;
typedef struct
{box data
[3005];int size
;
}heap
;
heap minh
;
int n
,m
;
int path
[1005];
void init(heap
&h
){h
.size
=0;h
.data
[0].cost
=-1;
}
void insert(heap
&h
,box a
){int i
=++h
.size
;for(;i
>0&&a
.cost
<h
.data
[i
/2].cost
;i
/=2){h
.data
[i
]=h
.data
[i
/2];}h
.data
[i
]=a
;
}
bool
judgeroot(box a
){while(path
[a
.x
]!=0) a
.x
=path
[a
.x
];while(path
[a
.y
]!=0) a
.y
=path
[a
.y
];if(a
.x
==a
.y
) return false;else {path
[a
.x
]=a
.y
;return true;}
}
box
del(heap
&h
){box min
=h
.data
[1];box last
=h
.data
[h
.size
--];if(h
.size
==0) return min
;int i
=2;for(;i
<=h
.size
;){if(h
.data
[i
].cost
>h
.data
[i
+1].cost
&&i
<h
.size
) i
++;if(h
.data
[i
].cost
<last
.cost
) {h
.data
[i
/2]=h
.data
[i
];i
*=2;}else break;}h
.data
[i
/2]=last
;return min
;
}
void swap(int
& a
,int
&b
){int temp
=a
;a
=b
;b
=temp
;
}
void Kruskal(){int v
=0,mincost
=0;while(v
!=n
-1&&minh
.size
!=0){box a
=del(minh
);if(judgeroot(a
)){v
++;mincost
+=a
.cost
;}} if(v
!=n
-1) printf("-1\n");else printf("%d\n",mincost
);
}
int
main(){box a
;scanf("%d%d",&n
,&m
);for(int i
=0;i
<m
;i
++){scanf("%d%d%d",&a
.x
,&a
.y
,&a
.cost
);insert(minh
,a
);}
Kruskal();
}
總結
以上是生活随笔為你收集整理的08-图7 公路村村通 (30分)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
