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