小生成樹(shù)并查集最短路-文庫(kù)吧資料
2025-05-21 11:21本頁(yè)面
【正文】 題目分析 : ?該你們練習(xí)了～ 參考源碼 (HDU1232) ? include ? int bin[1002]。 } 再一題 — 暢通工程 (HDU1232) ? 題目描述： 某省調(diào)查城鎮(zhèn)交通狀況，得到現(xiàn)有城鎮(zhèn)道路統(tǒng)計(jì)表，表中列出了每條道路直接連通的城鎮(zhèn)。 return father[p]。 ? i = j。 ? while (i r) //本循環(huán)修改查找路徑中所有節(jié)點(diǎn) ? { ? j = set[i]。 ? while (set[r] r) //循環(huán)結(jié)束，則找到根節(jié)點(diǎn) ? r = set[r]。 return r。 } find2(x) { r = x。 } else if (height(a) height(b)) set[a] = b。 } Θ(1) 最壞情況 Θ(N) 一般情況是 …? 并查集 ? 性能有本質(zhì)改進(jìn) ? ? 如何避免最壞情況 ? 并查集 ? 方法 ：將深度小的樹(shù)合并到深度大的樹(shù) ? 實(shí)現(xiàn) ：假設(shè)兩棵樹(shù)的深度分別為 h1和h2, 則合并后的樹(shù)的高度 h是 : ? max(h1,h2), if h1h2. ? h1+1, if h1=h2. ? 效果 ：任意順序的合并操作以后，包含 k個(gè)節(jié)點(diǎn)的樹(shù)的最大高度不超過(guò) ? ?klg并查集 merge3(a,b) { if (height(a) == height(b)) { height(a) = height(a) + 1。 } merge2(a, b) { if (ab) set[b] = a。 while (set[r] != r) r = set[r]。 k++) { if (set[k] == j) set[k] = i。 for (k=1。 } Merge1(a,b) { i = min(a,b)。 這部分涉及到了集合操作，也就是我們馬上要講的 并查集 并查集 英文： Disjoint Set，即 “ 不相交集合 ” 將編號(hào)分別為 1… N的 N個(gè)對(duì)象劃分為不相交集合， 在每個(gè)集合中，選擇其中某個(gè)元素代表所在集合。 } } 最小生成樹(shù) 整體思想已經(jīng)完成，但是可以看到第二部分紅色字體標(biāo)出的代碼： sn1=findroot(m1), sn2=findroot(m2)。 sort(e,e+m,cmp)。e[i].y,amp。 i++) scanf(%d%d%d,amp。 for(int i=0。amp。 } 最小生成樹(shù) int main(){ while(scanf(%d,amp。 } if(k!=n) res=1。 //生成數(shù) +1 unionset(sn1,sn2)。 I f(sn1!=sn2){ res+=e[j].w。 jm){ //需要 n1條邊 int m1=e[j].x, m2=e[j].y。 //初始化集合數(shù)組 while(kn amp。 i=m。 //n定點(diǎn)數(shù)量， m邊數(shù)量，father[M],每個(gè)定點(diǎn)所屬集合 最小生成樹(shù) int kruskal(){ int res=0,k=1,j=0。 //表示 x到 y需要花費(fèi) w }e[M]。依次類推，直至森林中只有一棵樹(shù)，也即子圖中含有 n1條邊為止 。 最小
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1