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

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模板題。