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的形式，減低運算次數。

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]而來。

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

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](記得要走回原點)哪一個最小就是答案。

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

UVa 10779 Collectors Problem

題意：
    有N個人(含Bob)以及M種貼紙(編號1~M)，每個人手上有不同種類的貼紙數張，Bob要透過和別人交換貼紙使得他擁有最多種類的貼紙。交換規則為，除了Bob以外的其他人只與Bob交換，且只有當手中該種類貼紙大於1張時才會交換沒有的種類，也就是Bob要用某甲手中沒有的貼紙種類與某甲交換，且某甲只當該種類他有大於1張時他才願意換出那張貼紙。
    輸入第一行N M，接下來N行，每行第一個數字K表示那個人有K張貼紙，後面K個數字分別為每張貼紙的種類編號。N行中第一行為Bob。
    輸出Bob最多能擁有幾種貼紙。

想法：
    建圖做最大流，建圖方法為：

1. 每個人i擁有j種類貼紙d張，則cap[i][j]=d，表示人與該種貼紙之間的容量為那個人擁有該種貼紙的張數。
2. "除了Bob以外"，每個人i如果擁有j種類貼紙(也就是cap[i][j]>=1)，則將cap[i][j]--，因為他要保留一張絕對不交換出去，如果cap[i][j]==0，表示那個人沒有j種類貼紙，所以他願意換入該種類貼紙1張，因此把cap[j][i]=1。
3. 因為最後只要輸出Bob有幾種貼紙，建立每種貼紙到super sink(T)的容量為1。

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値加大。

UVa 825 Walking on the Safe Side

題意：
    從左上角走到右下角，只能往右走或是往下走，有障礙的點不能走，問左上走到右下共有幾種方法？

想法：
    高中排列組合題目，dp[i][j]的方法數一定是從dp[i-1][j]和dp[i][j-1]相加而來。

UVa 11389 The Bus Driver Problem

題意：
    有n個司機，早班有n條路線，晚班也有n條路線，這2n條路線都有不同的距離，要安排每一個司機早班和晚班各一條路線，但是如果早班+晚班的路線距離超過d的話，超過每1單位就要加班費r元，求如何安排路線給每位司機使得全部加班費為最小，並輸出。

想法：
    將早班n條路線由小到大排序，晚班也是，為了使得加班費總和最少，安排時就要盡量填滿d，因此早班最短配上晚班最長路線，然後早班第二短配上晚班第二長,.....依此類推。如果最短配上最短，會導致該路線和遠小於d，表示浪費了這位司機還剩下的距離，因此要盡量讓每位司機平均填滿d。

UVa 11833 Route Change

題意：
    第一行有N M C K四個數字，N表示有N個地點(編號0~N-1)，M表示有M條路線，C-1為終點編號，K為出發點編號。
    底下有M行，每行u v d三個數字，分別表示u到v和v到u這條路線需要花費d元。
    本題特別的要求為，0~C-1為特殊地點，只要踏入0~C-1這C個地點內，例如i這個點<=C-1，之後的路徑就只能依照i, i+1, i+2, .....,C-1這樣走，只要不在特殊地點，就能前往任意其他地方，本題求K到C-1的最小花費。

想法：
    依題目輸入將M條路線建好dis[u][v]=d，其他沒有連通的路線為INF。輸入完成後我們將編號小於C-1的點i，算出dis[i][C-1]，等等SPFA用到。
    然後做K到C-1的SPFA最短路徑，注意如果踏入的點(nxt)為特殊地點(nxt<C)，不要丟入queue裡面，而是直接判斷cost[C-1]=min(cost[C-1], cost[nxt]+dis[nxt][C-1])，其他不是特殊地點的nxt，則依照一般SPFA把nxt丟入queue即可。

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衣服的數量；然後做最大流，並判斷最後的數量是否與人數一樣。

UVa 820 Network Bandwidth

題意：
    求S到T的最大流量為多少。網路是雙向連接的，但共用頻寬，例如A B 10，則A到B的流量+B到A的流量要小於等於10。另外這題給測資的方式會有可能給你很多組A B Xi，所以A到B的頻寬要把Xi全部加起來，例如底下例子1~2的頻寬為30。
2
1 2 2
1 2 10
1 2 20
想法：
    Maximum Flow模板題。

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

POJ 1860 Currency Exchange

題意：
    假設有A，B兩種貨幣，要將A換成B，須透過匯率Rab和手續費Cab，因此實際得到B貨幣=(A-Cab)*Rab元。  
    第一行輸入N, M, S, V，N表示共有N種貨幣(1<=N<=100)，M表示底下有M行，每一行有六個數字A,B,Rab,Cab,Rba,Cab，Rab表示A換成B的匯率，Cab表示A換成B需要扣除的手續費，Rba和Cba同理。現在Nick有第S種貨幣V元，題目問Nick透過不斷交換貨幣，然後最後換回第S種貨幣的時候能否大於V元?

想法：
    用SPFA演算法，初始除了Dis[S]=V以外Dis[i]都是0，然後不斷更新Dis的值使其盡可能大，最後判斷Dis[S]是否大於V。

POJ 1125 Stockbroker Grapevine

題意：
    N表示共N個點，然後底下N行，第i行第一個數字t表示後面有t個pair，每個pair兩個數字分別代表x, w，i點到x點距離w，注意這是單向道路。題目求從哪個點當作起點可以使得該點走到距離該點最遠的距離為最短。假設i點作起點，走到距離i點最遠的那個點距離為Di，求所有Di中最小的那個值，輸出i及Di。另外題目要求這個i點需要能夠到達所有其他的點。
想法：
    先做Floyd演算法，再去找每個點i的Di，在從Di中選出最小的那個去輸出i及Di即可，注意要判斷這個i是否能到達所有除了i以外的點。

POJ 1724 ROADS

題目：
    總共N個點，給定R條道路，每條共有S,D,L,T代表S點到D點這條路長度L且須花費T元，題目求從1為起點，N為終點，在花費<=K元的情況下走到終點的最短距離。
    注意同一個S到D可能有多條道路。
想法：
    用Dis[i][j]表示"從起點1走到i點花費j元的最短距離"，所以做SPFA的時候，每次就去更新Dis[i][0~K]的值，使其值盡可能的小，最後再去檢查Dis[N][0~K]的最小值是多少。
    因為S到D可能有多條道路，所以用vector來存較為簡單。

UVa 10986 Sending email

這題就是簡單的Shortest path問題，用SPFA即可解決。

UVa 10801 Lift Hopping

題意：
    有n個電梯(1<=n<=5)，每個電梯移動一層樓的時間不一樣，第i個電梯每層樓的移動時間以T[i]表示，而每個電梯能到達的樓層也不一樣，如果兩個電梯都能到達x樓，則能在x樓換另一台電梯搭乘，但轉換的時間為60秒。今天起點在第0樓，給定第k樓為要前往的樓層，問最短的時間?
想法：
    先以Weight[i][j]表示在'不轉換'電梯的情況下，i樓到j樓所需的最短時間，這個部份可以在輸入測資的過程中一起完成。然後再考慮轉換電梯的情況，以Dis[i]表示到達i樓的時間，用SPFA演算法，每次queue的時候就判斷 if (Dis[now] + Weight[now][nxt] + 60 < Dis[nxt]) 來不斷更新Dis[nxt]的值。

UVa 10557 XYZZY

題意：
    總共有N個節點(1~N)，一開始起點在1且有100的能量，踏到每個節點都會有不同的能量變化(-100~+100)，目標是要走到終點N且過程中能量不能歸0。
想法：
    用SPFA演算法，不過要注意過程中可能會碰到正環或是負環，且有正環也不一定能走到終點，因為題目給的是單向的所以有可能走到正環的路走不到終點。因此可以假設如果走了100萬次(數字不一定)還是走不到終點就判定為無法到達。

UVa 10278 Fire Station

題意：
    有F個消防站分布在I個路口，假設每個路口i到離該路口最近的消防站距離為di，而D為這些di的最大值。今天要再增加'一個'消防站在某個路口，求要設在哪個路口使得D為最小。
想法：

1. 先用Floyd演算法求出All pair shortest path
2. 然後求各個路口i到離該路口最近的消防站的距離，用shortest_lenght[i]來存，並找出D值。
3. 從1開始枚舉到I，找出能使得D值最小的路口的編號。