最小生成樹(shù)和并查集
杭電關(guān)于最小生成樹(shù)分類(lèi)的幾個(gè)題目
摘要: HDU 1116 Play on Words
這個(gè)題目要運(yùn)用到歐拉路得相關(guān)知識(shí)，并且也要并查集，題目說(shuō)的是：給你n個(gè)單詞，要你判斷這些單詞能不能首尾相連。
理解題目意思后，進(jìn)行轉(zhuǎn)化，輸入字符串，提取首位字母作為下標(biāo)來(lái)表示兩節(jié)點(diǎn)的出現(xiàn)，以及相對(duì)應(yīng)節(jié)點(diǎn)入度和出度的增加，
轉(zhuǎn)化為并查集的應(yīng)用即可。那么從可以想象一幅由首位字母節(jié)點(diǎn)構(gòu)成的圖，當(dāng)且僅當(dāng)圖是一條歐拉回路或者歐拉通路的時(shí)候，
才能滿足題目的要求，至于歐拉回路和歐拉通路的判定可以總結(jié)為如下：
1）所有的點(diǎn)聯(lián)通
2）歐拉回路中所有點(diǎn)的入度和出度一樣。
3）歐拉通路中起點(diǎn)的入度 - 出度 = 1，終點(diǎn)的 初度 - 入度 = 1， 其他的所有點(diǎn)入度 = 出度；
閱讀全文
摘要: HDU 1301 Jungle Roads
這個(gè)題目的意思就是說(shuō)給你n個(gè)相關(guān)點(diǎn)，用A - I 來(lái)表示，然后給出n-1行，第 i 行表示從點(diǎn) i 到其他點(diǎn)的相關(guān)信息。
在給出的map的基礎(chǔ)上，要求選擇適當(dāng)?shù)穆肪€，使得所有給出的點(diǎn)都能夠到達(dá)任意其他點(diǎn)，問(wèn)題規(guī)模不大，直接矩陣
存儲(chǔ)，利用prim 算法搞定。
閱讀全文
摘要: HDU 1233 還是暢通工程
題目意思就是給你一個(gè)有n個(gè)點(diǎn)的圖，給出n *（n-1）/ 2 條邊的信息，包括邊的端點(diǎn)和邊的長(zhǎng)度，要求
在滿足所有點(diǎn)在同一個(gè)連通分支上的前提下，選擇最短的道路來(lái)修建。典型的最小生成樹(shù)算法，同樣，問(wèn)題
規(guī)模不大，直接矩陣就可以勝任。
閱讀全文
摘要: HDU 1102 Constructing Roads
這個(gè)題目的意思就是說(shuō)，給你一個(gè)有n個(gè)村莊的地圖，map[i][j]表示從村莊 i 到村莊 j 的距離，然后給你
m 條已有道路，讓你在這個(gè)基礎(chǔ)上添加適當(dāng)?shù)牡缆罚沟盟写迩f之間都是聯(lián)通的，求添加道路的最短距
離的值。
閱讀全文