UVa 10806 Dijkstra, Dijkstra

題意：
    給你一個無向圖，每條邊有cost，現在問如果不走已經走過的邊，則從S到T，然後再從T到S的最少cost是多少，如果無法達成則輸出"Back to jail"。

想法：
    最小cost最大流，S到T再從T到S，也就是T當作源點，S當作匯點，從T流到S，看是否能流過去2條，如果能則輸出min_cost，否則輸出"Back to jail"。
    因為同一條邊不能重複走，因此可以用一個二維矩陣used[][]，在SPFA找"正向邊"的時候檢查used[i][j]!=true，除了code 82行和96行之外，其他都和MCMF模板一樣。

UVa 10746 Crime Wave - The Sequel

想法：
    銀行編號1~N，警察編號N+1~N+M，源點S=0以及匯點T=N+M+1。一開始先將S連到每間銀行，每個警察連到T，以及每間銀行連到每個警察，以上單向邊容量都為1。
    接下來就是套模板做MCMF，注意輸出的時候因為是double，因為進位問題所以要把答案加上一個極小的數字，例如，如果printf("%.2f", 17.225);，結果是輸出17.22，因此要printf("%.2f", 17.225+0.000000001);才會是正確答案17.23。

UVa 563 Crimewave

想法：
    點與點之間的邊是雙向邊，但是走某一邊後另一邊就不能走了，所以我們把一個點i分成兩個點i和i'，i到i'容量為1，點i建圖的時候：

• cap[i][i']=1
• 假設j在i的上方，cap[i'][j]=1，上下左右依此類推

    然後我們還要有個super source(S)和super sink(T)，把最外面四個邊的點i'連到T，S連到輸入的座標i(也就是銀行的位置)。建完圖後，就是做最大流看結果是否等於銀行的數量即可。

    一開始TLE了，後來用了個vector<int> edge[MAX]來存每個點i能連到哪些點，避免bfs的時候nxt要從0到最後(程式碼81行)，最後時間為1.8s。

UVa 10594 Data Flow

題意：
    給你一個無向圖，兩點之間的邊的容量是K，每條邊有不同的cost，現在有大小為D的資料，要從起點傳到終點，問把全部資料傳過去的最小cost是多少，如果不能全部傳過去則輸出Impossible.

• 第一行輸入N M：總共N個點，編號從1~N，然後底下有M行
• 有M行，每行u v c：表示點u和點v之間的cost為c(雙向圖)
• 最後一行D K：要傳的資料大小為D，每個邊的容量為K

想法：

    最小cost最大流題型(MCMF)，基本上就是建圖，然後套MCMF演算法模板，但提交後發現時間根本是壓秒過@@，花了2.979s(時限3s)，但是這個秒數排名還在前一半以內...。

    不過還是要壓一下秒數，看了同學的code後，發現這題可以最佳化的地方在於"每條邊的容量都是一樣的"，所以你可以把每條邊的容量當成1，然後再乘以K就好了。底下附上兩種code，第一個是差點TLE的模板code，第二個是最佳化的code，兩者的差別只差在MCMF()這個function的寫法。第二個的時間是0.135s， 和原本差了20幾倍。

UVa 10364 Square

想法：

    dfs加上各種減支：

1. 如果所有stick的長度和(sum)不能被4整除直接輸出no
2. 如果最長stick的長度已經大於(sum/4)直接輸出no
3. dfs的時候已經排完三個邊直接return true，因為第四個邊一定排得出來
4. 先將stick由大排到小，每次dfs的時候stick不要從第一個開始挑選，而是要從上一層dfs選到的stick的下一個開始選。

基本上第四點是關鍵，有跟沒有就是0.0x秒和TLE的差別。

UVa 11218 KTV

題意：
    總共有9個人(編號1~9)要分成3組唱歌，每組3個人，每個人只能唱一次。第一行N表示底下有N種組合，每種組合a,b,c,s，前三個是人員編號，s是該組合的分數。從N種中任選三種組合使得1~9號都能唱到歌，並且使得分數的和最高，輸出該分數，如果找不到組合滿足大家都能唱到歌則輸出-1。

想法：
    bitmask，(1<<9)-1表示所有人都唱的到歌的狀態，二進位來看就是(111111111)2，dp[i]=j表示在狀態i的情況下最高分數為j，因此dp[(1<<9)-1]就是所有人唱的到歌的最高分數。
    用dfs來枚舉不同組合，當人員沒有重複的時候才能將兩個狀態合併在一起，例如(000000111)2和(000111000)2這兩個狀態可以合併變成(000111111)2，並去更新dp[(000111111)2]的分數，不斷更新所有可能的合併來枚舉所有情況。

UVa 10651 Pebble Solitaire

題意：
    跳棋，例如"oo-"表示第一和第二個位置有棋子，第三個位置是空的，因此第一個位置的棋子可以跳過第二個位置的棋子並取走第二個位置的棋子，變成"--o"。題目給定一個12個位置的棋盤，問經過不斷跳棋後，剩下最少棋子的數量。

想法：
    想到兩種方式：bitmask+bfs或是backtracking，兩種方法其實差不多，都是把所有的情況枚舉，找出最小値。第一種方法為0.009s，第二種為0.012s，時間相差不大，寫backtracking是較簡單的。

UVa 10199 Tourist Guide

題意：
    LuckyCat中文翻譯，基本上就是求所有Cut Vertex。

想法：
    Cut Vertex模板。

UVa 247 Calling Circles

題意：
    LuckyCat中文翻譯
想法：
    SCC Tarjan演算法模板，將每個SCC的朋友名字都存下來，然後一行一行輸出。

UVa 11838 Come and Go

題意：
    題目求這個城市是否為一個強連通的城市(從任意點出發可以抵達每個點)，第一行會給N個點和M條路，底下M行每行有V,W,P，如果P==1表示該條路為單向V->W，P==2則是雙向V<->W。

想法：
    SCC模板，檢查scc_cnt是否為1，因為scc_cnt==1表示整個graph都可連通。

UVa 315 & POJ 1144 Network

題意：
    critical point指的是在一個connected graph中，如果移除該點，會使得該graph不再connected，則該點為critical point(cut vertex，割點)，現在給你一個graph，求critical point的數量。
    給你一個N表示共有N個點，底下最多N行，以0表示本次case輸入完畢，每行有a,b1,b2,b3.....，表示(a,b1),(a,b2),(a,b3)為邊，記得建邊的時候為雙向。

想法：
     cut vertex模板題 。

UVa 10080 Gopher II

題意：
    有N個地鼠和M個地鼠洞，每個點都有座標(x,y)，因此每隻地鼠和每個地鼠洞之間有不同的距離，每隻地鼠的移動速度都是v，現在有老鷹會在s秒後抓沒有跑進洞的地鼠，一個地鼠洞只能藏一隻地鼠，求沒有躲到洞裡被老鷹抓走的地鼠的最少數量為?

想法：
    地鼠在左邊，地鼠洞在右邊，把每隻地鼠與能在時間內跑到的地鼠洞都建一條邊，然後做最大匹配，答案就是(地鼠數量-最大匹配數)。

UVa 1194 & POJ 1325 Machine Schedule

題意：
    有A,B兩台機器，A的mode從0~n-1，B的mode從0~m-1，現在有k個job，底下有k行，每行有三個數i,x,y表示第i個job，A機器需用mode(x)完成這項工作，B機器則是需用mode(y)，一向工作只需交給A或B其中一個即可。有個規則是A,B這兩台機器變換mode的時候需要restart一次，例如mode(1)變成mode(10)需要restart一次，一開始兩台機器都是從mode(0)開始，問如何分配工作給A或B使得總restart次數最小，並輸出restart次數。

想法：
    一件工作x,y如果選x則不用y，反之選y就不用x，但都是要restart一次，因此可以想到最大匹配數，如果x或y其中一個已經匹配好了，表示A或B其中之一已經restart一次，則這件job就可以跳過。
    具體做法是，將第i個工作x放到左邊那群，y放到右邊那群，並建立(x,y)這條邊，然後套模板求最大匹配數就是答案。注意讀入測資的時候如果x或y其中是0，則直接跳過不用建邊，因為機器從mode(0)開始。

UVa 663 & POJ 1486 Sorting Slides

想法：
    做最大匹配，做完可從llink[i]=j得到每條匹配的邊(i,j)，也就是(i,j)是可能的答案，但要確認這條邊(i,j)的唯一性。
    例如Sample Input的第二個測資，做完最大匹配可得到(A,1)(B,2)兩條邊，最大匹配數為2，要確認(A,1)是否唯一，就把(A,1)這條邊去掉並且禁止，然後再做一次最大匹配，會變成得到(A,2)(B,1)，最大匹配數還是2，與數量原來一樣並沒有減少，因此可知(A,1)這條邊不唯一。同理(B,2)也把它去掉並禁止，再做一次最大匹配，如果最大匹配數比原本小，這條邊就是答案可以輸出，反之如果最大匹配數和原本一樣，則這條邊不唯一不能輸出。
    從底下code可以看到最大匹配的模板函數Bipartite(int n, int u, int v)多了兩個參數u, v，表示做最大匹配的時候禁止(u,v)這條邊的使用(line 65)。

UVa 10349 Antenna Placement

題意：
    如題目的圖，一個圓圈最多能圈住兩個'*'，現在問一幅圖有n個'*'，最少用多少個圓圈就能把所有'*'圈住？

想法：
    最大匹配問題，將圖上所有點分成兩群相間隔，例如
101010
010101
101010
    在編號1的'*'建一條邊連到S(Super Source)，在編號'0'的'*'建一條邊連到T(Super Sink )，然後相鄰的'*'彼此也建一條邊，這些邊的容量都是1，建完邊後套一次最大流模板，就是最大匹配數。
    做最大匹配得到的結果不是真正的答案，例如*****五個'*'的最大匹配是2，答案則是(5-3)，因此本題答案為(所有'*'數量-最大匹配數)。

UVa 10313 Pay the Price

題意：
    LuckyCat中文翻譯

想法：
    用dp[i][j]=k表示i元最多用j個硬幣有k種方法，詳細註解在底下code：

UVa 10465 Homer Simpson

題意：
    有兩種漢堡A和B，吃一個A需要m分鐘，吃一個B需要n分鐘。現在給你t分鐘，問在"剛好用完"t分鐘的情況下最多能吃幾個漢堡k，輸出k；如果沒辦法剛好用完t分鐘，則找最接近t分鐘的k値，輸出k和差幾分鐘。

想法：
    背包問題，重量和物品價值都是時間，Time[i]=k表示給你i分鐘最多能用到k分鐘，如果Time[t]==t表示剛好用完t分鐘，否則最多就是用到Time[t]分鐘，差t-Time[t]分鐘；另外用num[i]=k用來記錄i分鐘能吃k個漢堡。

UVa 10130 SuperSale

題意：
    有一家超市有N種商品正在做特價，每種商品數量無限，但規定一個人每種只能買一個，P表示該種商品價值P元，W表示該種商品重W。現在有一家庭共G人，每個人都有不同的背包重量上限MW，問這一家人能買到最高商品價值為多少?

想法：
    背包問題，dp[MW]=k表示重量上限MW的背包裝的物品最多價值k。

UVa 674 Coin Change

想法：
    用method[i]=k表示i元有k種方法，枚舉所有錢幣，假設該錢幣為j元，則method[i+j] = method[i+j] + method[j]，表示method[i+j]的一部分方法數是由method[j]而來。

UVa 10944 Nuts for nuts..

想法：
    狀態壓縮DP題目，假設Larry編號為0，堅果編號從1~N，一開始先將任兩點距離算好，因為移動是八個方向，所以dis[i][j] = max(|x[i]-x[j]|, |y[i]-y[j]|)。
    接下來做dynamic programming，定義dp[i][j]這個矩陣用來存最短步數：

• i為該狀態最後收集到的堅果編號
• j表示該狀態

    狀態的表示是用二進位，例如有5個堅果，若j=22則二進位為10110，表示編號2,3,5號的堅果已經被收集過了。那麼dp[3][22]就是在2,3,5號堅果已經收集且3號堅果是最後被收集的最短步數。
    定義完成後，首先先將dp初始化成INF，然後對於dp[i][1<<(i-1)]初始化成dis[0][i]，因為dp[i][1<<(i-1)]就是從起點走到編號i堅果的最短步數。然後以上面例子繼續，5個堅果，從狀態0 (00000)開始，一直遞增枚舉到狀態((1<<N)-1) (11111)就算完成。
    每次枚舉一個狀態i，例如10110，已經被收集的堅果編號j(也就是2,3,5)；沒有被收集的堅果編號k(也就是1,4)，然後再用迴圈跑這些已經被收集的編號j，每次就以這個編號j為最後被收集的編號(也就是dp[j][i])，加上j到k的距離去更新dp[k][i+ (1<<(k-1))]。整個式子
        dp[k][1+ (1<<(k-1))] = min(dp[k][1 + (k-1))], dp[j][i] + dis[j][k]);
   
    最後在檢查dp[1~5][11111]+dis[1~5][0](記得要走回原點)哪一個最小就是答案。

另外<<這個運算符的順序很低，所以括號要記得加。