POJ 1226 Substrings

想法：
    先將全部的字串依照length由小到大排序，把最短的那個字串拿來枚舉，由長到短枚舉該字串的所有substring，以sample input第二個case舉例，最短的字串為"rose"，枚舉substring "rose", "ros", "ose", "ro", "os"...。
    每次枚舉到一個substring後，記得還有反轉sub_inverse，把substring和sub_inverse拿來和其他字串(除了最短的字串以外的字串)比較，這邊我是套KMP Algorithm，如果其他字串全部都找的到substring或sub_inverse的話，表示找到答案，輸出該substring的長度。

POJ 3461 Oulipo

題意：
    找出W字串在T字串中出現幾次。例如W="AZA",T="AZAZAZA"，答案為3次。

想法：
    套KMP演算法

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]來紀錄答案，如果重複的題目就直接輸出即可。

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，也是這個測資的解答。

POJ 1523 SPF

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

想法：
    Cut Vertex模板。

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 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)。

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次就可以了。

POJ 1384 Piggy-Bank

題意：
    存錢桶重量E，裝滿硬幣的時候重量為F，現在有N種硬幣，每種硬幣的價值為P重量為W，問這個存錢桶至少為多少錢？

想法：
    最小背包問題，先將dp[i]初始化成INF，將最大背包的max()改成min()就可以了。

POJ 2392 Space Elevator

題意：
    K種不同的磚塊，每種磚塊的高度為h，能蓋的最大高度為a，數量為c，由於安全考量，所以當現在蓋的高度超過該種磚塊的a時，就不能再用該種磚塊，求最大能蓋的高度？
    例如sample input，第二種磚塊的高度為23，所以如果現在建築物蓋到24以上，就只能用第一種和第三種磚塊繼續蓋。

想法：
    這題要先將磚塊的a値由小到大排序，再做背包問題，算是一種greedy的方式，把a値小的磚塊盡可能放在底層，否則無法達到最大高度。
    例如底下左邊這組，答案是4，如果不排序成右邊的話，算出的結果會<4。
2         2
1 4 3     2 2 1
2 2 1     1 4 3
    且最後要枚舉一下dp的每個値找出最大値，因為最大値不一定位在dp的最後一個位置。

POJ 1276 Cash Machine

題意：
    不同價值Dk元的鈔票有Nk張，現在要求用這些鈔票能湊出最接近cash是多少元？

想法：
    背包問題，dp[i]=k表示i重量上限的背包最多能裝k價值的東西，題目給的Nk表示該物品的數量，而Dk是重量同時也是價值，這樣去求背包問題。因為這題時間限制，須採用和POJ 1024一樣的做法，將Nk件捆成1+2+4+8+16+32+....+left的形式，減低運算次數。

POJ 1014 Dividing

題意：
    每次有n1,n2,n3,n4,n5,n6六個數字代表價值1的大理石有n1個，價值2的大理石有n2個，....，價值6的大理石有n6個，現在要將這些大理石分成兩堆，問能否使得這兩堆價值一樣？

想法：
    背包問題，一開始單純把價值i的大理石做了ni次，例如價值5有70個，for迴圈就跑70次，結果就TLE了。
    後來學到其實可以將70 = 1+2+4+8+16+32+7，也就是ni=1+2+4+8+....+2^x+left，這樣可以大大減少for的次數，ni如果是70只要做6+7=13次。

POJ 2112 Optimal Milking

題意：

    有K台機器以及C頭牛，每台機器能容納M頭牛，且點與點之間距離不一樣，現在要分配每頭牛到某台機器，某一隻牛走到機器路徑最遠，假設為D，現在要使得D値最小，並輸出D値。

    輸入第一行為K C M，接下來有(K+C)*(K+C)矩陣，表示這(K+C)個點之間的距離(如果無法到達則為0)。

想法：

    先用Floyd解出任兩點最短距離，然後用二分搜尋去找D値，每次二分就建立一個圖並做最大流，並判斷最後到達牛的數量是否為M，如果是則D値可以更小，如果不是則要把D値加大。

1. 建圖方法為將每頭牛i和每台機器j之間的距離如果<=D，也就是dis[i][j]<=D，那麼把i,j兩個點之間容量設為1(cap[i][j]=1)
2. 每頭牛與super source(S)相連，容量為1
3. 每台機器與super sink(T)相連，容量為M

POJ 2455 Secret Milking Machine

題意：
    有N個點(編號1~N)組成無向圖，總共有P條邊，要找出從編號1走到編號N共T條路徑(也就是有T條從1~N的路徑)，使得這T條路徑最長的那條為最小。假設T條中最長的那條路徑長為D，我們要找出D的最小値。
     輸入第一行分別為N P T，接下來有P行，每行u v d表示有一條u到v距離為d的邊，注意u到v可能會有很多條邊，且這T條路徑不能重邊。

想法：
    二分搜尋+最大流，用二分去找D値，每次二分時就重新建一個新的圖，建圖方法為假設dis[u][v]<=D，就把[u][v]容量+1，建完圖後做最大流並確認是否有T條路徑，如果有則D値可以再小，如果沒有則要把D値加大。

1459 Power Network

題意：
    有發電站(只發電不耗電)，中繼站(不發電不耗電)，和用電站(只耗電不發電)三種node，題目求所有用電站耗電量總和的最大値。
    輸入第一行有4個數字，n np nc m，n表示共有n站，np為發電站數量，nc為用電站數量，m為有m條電線。
    接下來有m組(u,v)z，表示u到v該電線的容量為z。然後有np個(u)z表示編號u發電站發電量為z；再接下來有nc個u(z)表示編號u為用電站最大用電量為z。
想法：
    最大流模板題，用super source串起所有發電站，super sink串起所有用電站。

POJ 2584 T-Shirt Gumbo

題意：
　　以sample input舉例
START 4     -> 4表示有4個人
SM ML LX XT    -> 第一人能穿的衣服Size從S~M，第二人從M~L，...
0 1 1 1 0    -> 衣服S號有0件，M號有1件，L號有1件，X號有1件，T號有0件
END
    求出是否能將衣服分配給所有人。
想法：
    最大流題目，S表示super source，T表示super sink，S到每個人的容量為1，因為每個人只需要一件衣服；每種size的衣服到T的容量為該種size衣服的數量；然後做最大流，並判斷最後的數量是否與人數一樣。

POJ 2240 Arbitrage

題意：
    所謂"套匯"指的是透過不斷兌換成別的貨幣，最後再換成原本的貨幣會比本來的錢多。
想法：
    用R[i][j]表示i換成j的匯率，且初始化R[i][i]=1，做Floyd演算法後，去判斷R[i][i]是否大於1，如果大於1表示可以套匯。

POJ 2253 Frogger

題意：
    有隻青蛙要從位置1跳到位置2，假設某路徑途中單次最大跳躍距離為D，求出D的最小値。
    已sample input舉例，如果直接從(17,2)跳到(19,4)，D値為2，但如果從(17,4)跳到(18,5)再跳到(19,4)，D値為1.414。
3
17 4
19 4
18 5