UVa 10048 Audiophobia

題意：
    點與點之間的weight代表聲音的分貝大小，要找一條路徑所遇到的分貝最小，假設a到d某條路徑所遇到的最大分貝為100，另一條路徑所遇到的最大分貝為80，則後者那條路徑較佳。

想法：
    用Floyd演算法找All Pair Shortest Path。

UVa 10000 Longest Paths

    這題是找最長的路徑，我們可以用BellmanFord演算法，與找最短路徑相同的寫法，差別在於我們可以把點到點之間的路徑長變"負"的，最後找負最多的那個點就是最遠的點。

UVa 341 Non-Stop Travel

題意：
    Ruby兔中文翻譯
想法：
    用BellmanFord演算法找出最短路徑，並在找的過程中用Pre[i]紀錄什麼點走到i，最後在從終點利用Pre走回起點，並依題目輸出答案。

POJ 3259 Wormholes

題意：
    FJ要找出是否能從某個起點出發，然後回到該起點但可以遇見出發時的自己，也就是時間和要<0。

• 題目N表示有幾個點
• M表示有M行，每行S,E,T三個數字表示S點到E點或E點到S點所需要的時間是T
• W表示有W行，每行S,E,T三個數字表示S點到E點所減少的時間T，也就是S到E你的時間總和會-T，注意這個是單向的，只有S點到E點

想法：

    本題換句話說就是找出是否有負環(negative cycle)，確認在所有路徑中是否存在一個cycle，使得一直走那個cycle時間總合會越來越小。

POJ 2387 Til the Cows Come Home

這題其實就是要求終點走到起點的最短路徑，因此用個簡單的BellmanFord演算法即可解決這題。

UVa 10534 Wavio Sequence

Longest Increased/Decreased Subsequence
想法：
    替數列建LIS和LDS表，然後在從表中找出共同最大的數字。例如：
數列： 1 2 3 4 5 3 2
LIS：  0 1 2 3 4 0 0
LDS：  0 0 0 0 2 1 0
因此數字'5'的LIS為4,LDS為2，所以'5'為中心組成Wavio Sequence的長度就是min(4,2)*2+1=5。因此本題就從LIS和LDS表中找出最長的Wavio Seq長度。
    至於求LDS我是由後面往前作LIS，因此這題就是做兩次LIS，另外要注意如果用O(n^2)演算法可能會TLE。

UVa 437 The Tower of Babylon

題目：
    LuckyCat中文翻譯
想法：
    Longest Increased Subsequence題型，每種Block都有6種組合，所以每次讀入一組L,W,H，就存6種組合，等到全部讀完，就將全部的組合進行排序。因為我是打算將Block由小疊到大(做LIS，與題目相反)，所以排序方式就依L由小到大排，如果L一樣在依W排，然後就做LIS演算法。

UVa 836 Largest Submatrix

想法：
    這題是2維MSS(minimum subarray sum)，基本上第一個for loop先選出submatrix的垂直邊長，第二個for loop選定這條邊起始位置，然後向右做MMS。

UVa 507 Jill Rides Again

Minimum Subarray Sum
想法：
    這題求最大MSS值的區間，注意output說明，如果MSS一樣的話，要選擇最大的區間長度(j-i盡可能大)，如果區間長度又一樣長的話，那麼要選擇先出現的那個。

• 區間長度盡可能大：第18行要用">="
• 選擇最大區間長度：第24行的判斷式

UVa 231 Testing the CATCHER

Longest Decreased Subsequence
題意：
    Ruby兔中文翻譯
想法：
    由後往前用LIS。

UVa 111 History Sorting

題意：
    Luckycat中文翻譯。
想法：
    這題有個陷阱，以Sample input舉例：
10
3 1 2 4 9 5 10 6 8 7
4 7 2 3 10 6 9 1 5 8

由這行來看：3 1 2 4 9 5 10 6 8 7
"事件1在位置3"，"事件2在位置1"，"事件3在位置2"......"事件10在位置7"。

因此事件真正的排序是
10
2 3 1 4 6 8 10 9 5 7
8 3 4 1 9 6 2 10 7 5
然後再用LCS找出最大的長度。

UVa 10684 The jackpot

Maximum Sub-array Sum
想法：
    用DP做，設MSS為累加到目前的値，如果MSS是負的，那麼MSS=num，否則MSS+=num。

UVa 531 Compromise

Longest Common Subsequence題型
想法：
    用pre[i][j]來記錄LCS[i][j]是從哪個方向來的，再從pre[N-1][M-1]開始逆向走回並保存答案。

POJ 2421 Constructing Roads

想法：
    與POJ 1751是一樣的，先依題目將已連結的點連起來，剩下的再用Kruskal做最小生成樹，並累積最小生成樹的邊長和。

POJ 2395 Out of Way

想法：
    這題與POJ 1861一模一樣，求最小生成樹的最大邊長而已。

POJ 1861 Network

題意&想法：
     要找出最小生成樹MST，先輸出MST最長的邊長，再輸出MST有幾條邊(就是N-1)，然後在一一輸出這些邊的點。用Kruskal演算法找出MST，並依題輸出答案。
    ps.這題Sample Output有誤，4個點只需要3條邊就可以產生MST。

POJ 2533 Longest Orderded Subsequence

Longest Increasing Sub-sequence(LIS)題目
想法：
    這裡提供兩種方法：

1. 把已經讀入的數字存起來，每次讀一個新的數字i的時候，就把LIS[i]設成1，然後把現在這個新數字i與以前已經讀入的數字j做比較，如果i比j大且LIS[i]<LIS[j]+1，就把LIS[i]=LIS[j]+1。最後輸出最大的LIS值即可。
2. 與上面不同，LIS[]是存讀入的數字，一開始LIS[]是空的，慢慢放數字，每次讀入一個新的數字，從i=0，如果該數字>LIS[i]，就讓i++，直到在LIS表裡上不去為止，然後看該數字是否比LIS[i]小，如果是則更新LIS[i]的値。

POJ 1751 Highways

題意：
    依序給你N個城市的座標，然後接下M行說明哪些城市已經相連，題目要求盡可能用最短的距離把所有的城市連起來。
想法：
    先把兩兩城市的距離算出來，共有C(N,2)條邊長，將這些邊由小大到排序，然後做Kruskal演算法，將所有城市連起來。
    原本49~53行原本我是打算如果總共已經做了(N-1)條邊就跳出for loop，但是WA，後來想想應該是測資給的已經存在的邊會形成一個環(cycle)，所以就不可能為最小生成樹，邊長總數會大於(N-1)條。

POJ 1703 Find them, Catch them

想法：
    Disjoint Set題目，開兩倍陣列Set[2*N]，然後Set[i]表示與i是同Set，Set[i+N]表示與i為敵人，初始化先將Set[i]=i, Set[i+N]=0，其他詳細看底下Code。

UVa 11747 Heavy Cycle Edges

題意&想法：
    本題就是要把多餘的邊去除掉使得該graph變成最小生成樹，因此我們可以用Kruskal直接做出最小生成樹，然後把沒有用到的邊由小到大輸出即可。

UVa 10369 Arctic Network

題意：
    有S個衛星，以及P個城市，如果兩個城市都有衛星的話，那麼不管距離多遠都能通訊，否則就只能靠radio通訊，而靠radio通訊的最遠的兩個城市距離為D，現在求如果每個城市都要通訊的話，那麼D最小為多少?
以Sample Input舉例：
(0,300)~(0,600)=300之間，各使用一個satellite，透過satellite來溝通，(0,100)~(0,300)=200和(0,600)~(150,750)=212.13則使用radio，因此D至少要212.13

想法：
    P個城市代表有(P-1)條邊，而用Kruskal演算法做出最小生成樹，做Kruskal的過程中將邊長記錄下來，共有(P-1)條，然後把其中最長的(S-1)條邊分配給衛星，剩下的邊的最大値就是D。

UVa 10034 Freckles

題意：
    給你N個二維點座標，要找出把這N個點連在一起成一個Set的最短路徑
想法：
    先將點與點兩兩之間的邊長先算出來並排序，然後用Kruskal演算法，找出最小生成樹，並在找的時候同時將邊長累加起來最後即是答案。

淺談Backtracking演算法與其應用

    一般遞迴是把所有可能的路徑走過，也就是一一把答案枚舉(列舉)出來，然後再檢查答案的是否正確，但一一枚舉會非常耗時，而且常常枚舉出來的數量遠多於所需要的答案，原因在於在遞迴進行到一半的時候，如果該路徑是錯的，還是會不斷往下繼續遞迴，但其實我們可以在發現這條路徑不可能為答案的時候，就不要再往下遞迴下去，這就是Backtracking演算法。

POJ 1094 Sorting It All Out

題意：
    給定N表示有N個點，M表示底下有M行關係式，然後一行一行讀取關係式：

• 如果在第i行發現已經能明確將所有點排出順序(也就是只有一種答案)，輸出Sorted sequence determined after i relations: ...(順序)
• 如果在第i行發現和之前的關係式有衝突(形成一個環，例如A>B>C>A)，則輸出Inconsistency found after i relations.
• 如果讀取到最後關係都沒有衝突但也找不到唯一答案，則輸出Sorted sequence cannot be determined.

想法：

    每次讀取關係式的時候就檢查是否有衝突(形成一個環)，如果沒有再去找topological sort，topological sort這function裡面要判斷是否為唯一解，因此只能選一條路徑往下遞迴，最後判斷答案優先順序為1.先看有沒有衝突2.看有沒有解，再依題目敘述輸出即可，詳細看底下code。

POJ 2367 Genealogical tree

題意：
    第一行N表示有N個數(編號1~N)，接下來N行每行有幾個數字，第i行表示數字i需要在第i行那些數前面，例如Sample Input的4 5 1 0表示數字2需要在4,5,1的前面，以數字0代表該行的終止。

想法：
    建立graph，從起點(沒有其他點連入)開始用DFS走遍整個graph，並記下走過的順序，最後再逆向輸出就是一個topological sort。

UVa 872 Ordering

想法：
    這題是backtracking內融合了topological sort，基本上就是第一格, 第二格, ....依序填入，每次填的時後判斷哪些node可以填(表示需要在該node前出現的node已經出現過了)，詳細見底下code。

UVa 604 The Boggle Game

題意：
    在一個4x4 board裡找出所有符合的4個字元的單字，該單字須符合剛好只有2個母音('Y'也算母音)，每次Case有兩個board，找出這兩個board交集的所有單字。

想法：
    用DFS+backtracking先分別找出一個board的所有符合的單字，然後再將兩個board找出來的單字作交集：

UVa 193 Graph Coloring

題意：
    黑色不能相鄰，白色則不限制，如果編號最大的點是黑色的，則稱這個填入方法為optimal。題目給定一個graph，求填入最多黑色的方法，如果有多個答案，則盡可能選擇optimal的那種。

想法：
    MaxNum為填入最多黑色的點的數量，透過backtracking找出多種填入的方式，並不斷刷新MaxNum，並將該填法記錄下來，最後輸出最大MaxNum的填入方式，詳細見底下code。

UVa 10503 The dominoes solotarie

題意：

    給定N表示起點和終點之間要填入N個骨牌，給定M表示除了起點和終點外還有M個骨牌，每個骨牌兩端高度不一樣，因此一個骨牌用(p,q)來表示其兩端的高度。在放骨牌的時候，其相鄰的骨牌連接的那端高度需一致(例如一段骨牌放置如(a,b),(b,c),(c,d),(d,e))。起點(i1,i2)和終點(d1,d2)這兩個骨牌的兩端是不能交換的(不能變成(i2,i1))，而其它M個骨牌在放入的時候兩端是能交換的，因此這題要確認是否能在(i1,i2)和(d1,d2)之間放入N個骨牌。

想法：

    用backtracking確認是否能在起點和終點間放入N個骨牌。

UVa 291 The House Of Santa Claus

想法：
    這題的答案只從'1'當做起點，並將答案做遞增排序，用backtracking依序將答案找出。

UVa 598 Bundling Newspapers

題意：
    參考Lucky Cat。
想法：
    這題比較麻煩的部分在於輸入，輸入完成後就用backtracking把每個Size的答案找出來，詳細看底下code。

UVa 574 Sum It Up

想法：
    用Backtracking找出所有答案(包括這些答案可能重複)，之後在將這些答案依照遞減排序，再輸出，輸出時要確定這個答案之前是否已經存在了。

UVa 524 Prime Ring Problem

想法：
    用backtracking找出各種可能的組合方式，詳細看底下code：

UVa 11085 Back to the 8-Queens

想法：
    先建表，把可能的位置存下來(共92種)，然後再看哪種位置所需要的Move數量最低。話說原本不知道Queen原來像象棋的車，移動一步可以任意距離，害我吃了WA@_@

UVa 624 CD

想法：
    在小於等於限制的情況下一直遞迴找能放入的數字，並不斷刷新Maxsum(最接近限制的和)，詳細看底下。

UVa 989 Su Doku

想法：

    每次要填入一個數字時，確認該行與該列和該九宮格(box)裡面是否已經有這個數字，如果能填入，則繼續遞迴下去填下一格。

UVa 441 Lotto

想法：
    排列組合中的組合，因此每次挑選的時候只能比之前挑的數字還要大，用遞迴做Backtraking，詳細見底下code:

UVa 167 The Sultan's Successors

想法：
    這是一個八皇后問題，可以先將所有可能方式先記下來(共92種)，之後再輸入測資檢查這92種哪一種最大即可，如果還想更快的話，直接把這92種先輸出，然後直接寫在code裡XD。

UVa 10305 Ordering Tasks

想法：
    輸出只要符合是一個topological sort即可，因此可以從起點(沒有被任何點連入的點)用DFS走遍，並同時記錄走遍的點，最後再逆向輸出這些點就是一個topological sort。

UVa 11606 Pick up sticks

想法：

    把放在最上面(也就是這個點沒有其他點連入)的stick當做起點，用DFS走遍，並將走遍的經過的點記錄下來，最後逆向輸出這些記錄的點就是一個topological sort。

UVa 200 Rare Order

題意：
　　Input給的那些字串是每個index的名稱，而這些Index是照"某個字典序"由小到大排好的(就像一般的目錄是從A~Z排好)，我們要從Input裡面判斷這些字的字典序。例如Sample Input：
  XWY
  ZX
  ZXY
  ZXW
  YWWX
    我們可以從XWY和ZX判斷X<Z，ZXY和ZXW判斷Y<W，ZXW和YWWX判斷Z<Y，所以可以得到X<Z<Y<W。

**本題測資只有一個**

想法：
　　一次兩行判斷，找出誰<誰，記錄完之後，從沒有被連入的點當做起點，使用DFS走遍並記下走遍的點，將記下的點逆向輸出就是一個topological sort。

UVa 11060 Becerages

想法：
　　記錄每個點被其他點連入的數量(Ex: A->B, C->B，則beConnected[B]=2)，和記錄各個點連到哪些點。

1. 每次從頭找beConnected[i]==0(表示沒有點連到i)的Node
2. 將這個Node輸出
3. 同時將beConnected[i]改成-1表示這Node已經輸出過了
4. 然後其他每個被Node i連入的Node j，把beConnected[j]--
5. 執行1~4 N次，把每個Node都輸出過

POJ 2442 Sequence

想法：
　　這題與UVa 11997一樣，差別只在於UVa那題是K行K個數字，這題是M行N個數字，詳細過程我寫在UVa 11997 K Smallest Sums。

UVa 11997 K Smallest Sums

題意：
    有K行，每行有K個數字，從每行裡面各選出1個數字並加起來共有K^K種組合的和，輸出最小的K個和。

想法：
    我們可以先將第一行和第二行求出前K小的和，因此兩行數字就變成了一行數字，這一行數字再和第三行求出前K小的和，兩行又合併成一行，一直重複將兩行合併成一行，最後就是答案。
    因此現在關鍵是如何有效率求出兩行的數字前K個最小的和，如果暴力解的話為O(K^2)，很可能會TLE，用priority queue來解這題只要O(K)，過程如下：
*假設第一行數字陣列為L1，第二行數字陣列為L2，
*要丟進priority queue(底下簡稱PQ)裡的structure裡面含有兩個元素，第一個為val: 表示L1某個數+L2某個數的和，第二個為pos: 表示L2某個數在L2的位置(index)。

1. 將L1遞增排序
2. 將L2遞增排序。
3. 然後把L1裡面每個數字和L2[0]加起來，val=L1[i]+L2[0]和pos=0放到PQ裡面。
4. L1的數字就不會用到了
5. 之後每次從PQ裡面拿出第一個(最小的val)，將這個val放入L1(覆蓋以重複利用L1)，然後將這個val=(val-L2[pos]+L2[pos+1])和pos=pos+1丟回PQ裡
6. 重複步驟5 K次，L1裡面就有K個數字，表示這兩行已經合併成功
7. 讀入下一個L2，並重複步驟2~7，直到將K行合併成一行
8. 輸出L1

用這方法將兩行合併成一行的時候，只要做K次即可，因為我們已經將L1都丟進PQ裡面，然後每次都選最小和出來，並同時把可能的答案丟入PQ。

POJ 2255 Tree Recovery

想法：
　　原本的字串是整棵Tree，我們可先找到這個Tree的Root，再將其分為左右Sub Tree，一直遞迴下去直到Sub Tree只剩一個元素。
　　具體做法是：

1. 先用Preorder String找出Root(P_root)，再透過P_root找到Inorder String的Root(I_root)
2. 然後用I_root分別找出左右Sub Tree在Inorder String的左右界(會有4個index：左子樹的左右界和右子樹的左右界)，再用剛才4個index的結果來找出左右子樹在Preoder String的左右界(一樣有4個index)。
3. 依照Post Order的順序：
1. 先遞迴左子樹
2. 再遞迴右子樹
3. 輸出Root

底下有附詳細註解的Code：

UVa 11987 Almost Union-Find

想法：

• int Root[] : 表示i這個點存放在哪個Set(也就是Set[Root[i]]裡面可以找到i這個數字)
• vector<int> Set[] : 每個Set裡面可以存放很多數字

分成三個操作：

1. Union：如果x和y不在同個Set，那就把元素個數較少的那個Set裡面的每個元素移動到另一個Set，並同時將Root[]重新指向。例如Set[Root[y]]元素較少，就把Set[Root[y]]內的元素加入到Set[Root[x]]，並且把Set[Root[y]]的元素n，使得Root[n]=Root[x]。
2. Move：如果x和y不在同個Set，就把Set[Root[x]]這個Set內的元素x刪除，並在Set[Root[y]]加入x，記得將Root[x] = Root[y]。
3. Output：輸出Set[Root[x]].size()和該Set內每個元素的和。

UVa 11503 Virtual Friends

想法：
　　架構與UVa 10685 Nature一樣，差別在於這題每輸入一組測資就要把該組測資所在的Set的大小輸出。

UVa 10685 Nature

想法：

• Set[i]表示i這個node的father node(上面一層node的編號)，Root這個node的father node還是自己。
• Num[i]表示以i這個node為root的set，有幾個元素

這題與UVa 10608 Friends是一樣的，差別在於這題給的input為字串，因此我們先用map將它轉成數字編號。

UVa 10608 Friends

想法：
　　做Disjoint Set，詳細看底下Code~。

UVa 10583 Ubiquitous Religions

做disjoint set，架構與UVa 793 Network Connections一樣。

UVa 879 Circuit Nets

想法：
　　與UVa 793 Network Connections一樣，依題意做disjoint set，排名拿到Rank 2，可能這題做的人少吧XD

UVa 793 Network Connections

想法：
　　建disjoint set，把連在一起的電腦放在同一個Set，在判斷兩台電腦是否在同一個Set。具體做法是，

1. 一開始每台電腦都是一個Set(同時該Set的root就是該台電腦編號)
2. 然後要合併兩個Set就先各別找到它們的Root，再從一邊的Root連到另一邊的Root合併成一個Set
3. 要判斷兩台電腦是否在同一個Set也是分別找Root，如果Root一樣表示這兩台電腦在同一個Set。

POJ 3253 Fence Repair

想法：
　　題目雖然說是砍斷，但其實可以想成一塊一塊拼回來，兩塊兩塊拼成的長度就是收取的費用，這題跟 UVa 10954 Add All 做法一樣，用priority_queue。

POJ 2431 Expedition

題意：
　　一群牛從起點要出發到城鎮(目的地)距離共L單位，每走一單位同時消耗一單位的油，一開始油箱有P單位的油量，路途中會經過幾個加油站，每個加油站會給兩個數字，1.距離城鎮多少單位，2.這個加油站能加多少油，本題問到目的最少要到幾個加油站加油，如果不可能到達目的地則輸出-1。

想法：
　　因為所有地點都在同一直線上，所以都會經過每個加油站，只是看要不要停下來加油而已。所以我們就盡可能往前走，把每個路過加油站的該站的加油量放到priority queue裡面，然後直到走到途中沒油了，就從priority queue裡面拿出第一個(最大的加油量)加到自己的油箱，因為既然要加油，就要一次加最多的油，一直反覆這個動作直到終點。

UVa 12347 Binary Search Tree

想法：
    真的直接造出一棵樹來~

UVa 11995 I Can Guess the Data Structure

想法：

    既然C++提供STL了，那就直接拿來用，模擬實際情況，但取値或pop()的時候要注意該Container是否為empty，否則會Runtime Error。

UVa 10821 Constructing BST

想法：
    在最上層的時候，假設我們有數列{1,2,3,4,5,6,7}，要選出一個數字當作該層的root，例如選擇'4'，那麼{1,2,3}就被分配到左子樹，{4,5,6}到右子樹，到下一層我們一樣從{1,2,3}和{4,5,6}選出各自的root，然後繼續到下一層。
    但題目有說輸出要盡可能小，所以選擇root的時候，要盡可能選靠左邊的數字，所以要讓右子樹填滿，例如現在最上層數列為{1,2,3,4,5,6}，深度H=3，代表子樹深還有2，則左右子樹各別能提供(2^2-1=3)3個空間，因此我們選擇'3'當作root，分成{1,2}和{4,5,6}到左右子樹，讓右子樹3個空間被填滿，一直遞迴下去直到分配完全部數字。

UVa 10954 Add All

想法：
    這題不是單純由小加到大，考慮 4 5 5 6 7 這數列，4+5+5=14之後，應該要做6+7=13，之後再做13+14=27。
    因此每次都選擇兩個最小的數字相加，然後變成一個數字，然後丟回數列裡面，重複至數列只剩一個數字。
    借這題順便練習一下priority_queue，它有三個參數priority_queue<type, container, function>，container有兩種，可以用vector<>和deque<>，function也有兩個，less<>將最大的元素放在top，greater<>將最小的元素放在top。