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幾倍。

POJ 2411 Mondriaan's Dream

想法：

狀態壓縮DP，我們定義一列(橫的)一個狀態D：

• 第i位置為1表示這一列位置i和下一列位置i是由直長方形組成(|)
• 第i位置為0表示1以外的情況

注意以上的定義，以這題題目的圖來看，

• 第一列狀態D1=(00100001100)2
• 第二列狀態D2=(11010010000)2
• 第三列狀態D3=(00100001001)2
• 其他列依此類推，最後一列一定全部都是0。

接下來定義dp[i][d] = k，表示第i列在狀態d的情況下有k個方法數。如果能接受的話，那麼根據定義，如果第H列是圖的最後一列，本題答案就是dp[H][0]。

    定義完成後，基本上的做法是從最上面那列開始往下更新，例如第i列狀態a如果能和第i+1列狀態b相鄰(注意任兩個狀態不一定相鄰..)，那麼dp[i+1][b]+=dp[i][a];，就這樣枚舉所有狀態，最後輸出答案dp[H][0]。

    為了簡化code，不用初始化第一列每個狀態方法數是1(因為第一列所有狀態都是可以的)，因此我們直接初始化dp[0][0]=1，令這個假設的第0列狀態0方法數為1。

    另外在做以上的for loop之前，先建個狀態是否可以相鄰的表，令adjacent[i][j] = true表示狀態i在這列而狀態j在下一列是可以相鄰的，如最上面題目example，adjacent[D1][D2]==true，adjacent[D2][D3]==true。

    最後總結一下，為了加速，我們可以總是讓寬比較小高比較大，這樣可以減少每列的狀態數，另外也能用個ans[H][W]來紀錄答案，如果重複的題目就直接輸出即可。

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是較簡單的。

POJ 1753 Flip Game

想法：
    Bit運算，16位來表示棋盤的情況，16個0表示全白，16個1表示全黑。用BFS演算法，從一開始的情況開始出發，直到變成全白或全黑為止，或是無法變成全白或全黑。

POJ 2117 Electricity

題意：
    這題是將graph中移除一個點，graph會變成D個獨立部分，求D的最大値。
    第一行輸入P和C表示有P個點(0~P-1)和C條邊，每條邊都是雙向的。

想法：
    分成兩個

1. 如果C==0表示P個點沒有任何的邊，直接輸出P-1
2. 本來的圖就分成N部分(N可能==1表示所有點都是連通的，但N也可能>1)，移除某個點i能將該部分再分成cut[i]部分，那麼其中一個候選答案為N+cut[i]-1，找到最大的候選答案。套Cut Vertex模板求cut[i]。

    第二點舉個例子：

5 3

0 1

1 2

3 4

表示0,1,2和3,4不連通，所以N==2，N是固定的，然後例如移除點1，cut[1]==2(因為(0,1,2)這部分移除點1會將0,2分開變成2個部分)，因此候選答案就是2+2-1=3，也是這個測資的解答。

UVa 10199 Tourist Guide

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

想法：
    Cut Vertex模板。

POJ 1523 SPF

題意：
    基本上就是給你一個Network的Graph，然後求這graph的所有割點，以及如果去除掉該割點能將Network分成幾個部分。
    本題都是雙向邊，且每個測資是以1個0分開，最後結束也是1個0。

想法：
    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)，因此本題答案為(所有'*'數量-最大匹配數)。

POJ 1742 Coins

題意：
    有N種硬幣，每種硬幣價值A[i]元以及該種硬幣的數量為C[i]，問這些硬幣在最多總合為M元的限制下有幾種組合數?

想法：
    01背包，dp[i]=true表示i元可以被組合出來，最後看dp[1]~dp[M]有幾個true就是答案。這題時間限制嚴格，因此用POJ 1276那篇的方法還是會TLE，因此在底下code22行，我們知道如果j是從M~0表示一次放一個物品，每種要做C[i]次，現在22行j從0開始~M，是用無限背包的方式，先把物品當作無限個，類似greedy的方式，然後用個num陣列來計數，這樣每種物品都只要跑1次就可以了。