# 題目: UVa 681 - Convex Hull Finding # 題目說明 給N個點 (x, y平面座標)，求這些點的凸包(Convex Hull) INPUT: 第一行輸入一個整數T，代表測資數 每筆測資輸入一個整數N，接下來有N行，每行輸入兩個點(x, y)，為點的座標 輸入一個-1間隔測資 OUTPUT: 與輸入幾乎相同 區別在於N改為凸包的node數量，即分別輸出node的座標 起點需輸出2次 (頭尾) # 解題方法 能夠使用Graham's Scan演算法 或者Andrew's Monotone Chain演算法 Graham's Sca

# 題目: UVa 12125 - March of the Penguins # 題目說明 給一個座標圖，有N塊冰塊及數隻企鵝，要使企鵝全部跳到同一塊冰塊上，求哪幾塊可以? INPUT: 第一行輸入一個整數T代表測資數 每筆測資第一行輸入N、D，代表冰塊的數量、企鵝能跳的距離 接下來有N行，每行輸入四個整數x、y、n、m，代表點(x, y)有n隻企鵝，能跳m次 OUTPUT: 求哪幾塊冰塊能使所有企鵝跳到上面 # 解題方法 此題的解題概念為Maximum flow、Ford Fulkerson 將S連到所有冰塊上，capacity為企鵝的數量 將每個冰塊連接到企鵝能跳的的冰塊上，ca

# 題目: UVa 11506 - Angry Programmer # 題目說明 給M個node與W條edge及他們的capacity 求此圖的最小割 INPUT: 第一行輸入兩個整數M與W，代表有M個node與W條edge 接下來有M - 2行，每行輸入兩個整數U、C，代表node U的capacity為C 接下來有W行，每行輸入三個整數U、V、C，代表edge U V的capacity為C OUTPUT: 輸出此圖的最小割 # 解題方法 此題的解題概念為Maximum flow、Ford Fulkerson 最小割可以轉換成最大流 點上的capacity可視為兩個相連的點，edg

# 題目: UVa 11380 - Down Went The Titanic # 題目說明 給一個X * Y的圖，求*(人)能走到#(終點)的最大數量 * 碎冰上站著一個人(起點)，capacity為1 . 碎冰，capacity為1 @ 厚冰，capacity為無限 ~ 海，capacity為0 # 木頭(終點)，capacity為P INPUT: 輸入三個整數X、Y、P 接著輸入X * Y個char OUTPUT: 輸出*(人)能走到#(終點)的最大數量 # 解題方法 此題的解題概念為Maximum flow、Ford Fulkerson 點上的capacity可視為兩個

# 題目: UVa 10330 - Power Transmission # 題目說明 給N個點，M條邊，每個點及邊上有capacity 求此圖的maximum flow INPUT: 第一行輸入一個整數N，接著輸入N個整數，代表點1 ~ N的capacity 輸入一個整數M，接著有M行，每行輸入U、V、C三個整數，代表點U與點V連線，capacity為C 輸入兩個整數B、D 輸入B個整數，代表B與起點相連 輸入D個整數，代表D與終點相連 OUTPUT: 輸出maximum flow # 解題方法 此題的解題概念為Maximum flow、Ford Fulkerson 點上的cap

# 題目: UVa 12873 - The Programmers # 題目說明 有P隊隊伍，S個組別，每個組別最多能有C個隊伍 求參加隊伍的最大數量 INPUT: 第一行輸入一個整數T，代表測資數 每筆測資第一行輸入四個整數P、S、C、m 接下來有m行，每行有兩個整數u、v，代表u隊的組別為v OUTPUT: 輸出參加隊伍的最大數量 # 解題方法 此題的解題概念為Maximum flow、Ford Fulkerson 此題可視為一個S -> teams -> sites -> T的聯通圖 (起點連到隊伍、隊伍連到組別、組別連到終點) 找出此圖的maxflow即為答案

# 題目: UVa 11418 - Clever Naming Patterns # 題目說明 有N組字詞，裡面分別有N(K)個字 你需要從每組字詞中取出一個字，必須按照字母排序 例如題目中的: 3 2 Apples Oranges 1 Bananas 5 Apricots Blueberries Cranberries Zuccini Yams N為3，所以必須取3個字，且開頭須為A、B、C 我們取第一組的Apples 第二組的Bananas 第三組的Cranberries 排序後輸出 INPUT: 第一行輸入一個整數T，代表測資數 每筆測資第一行輸入一個整數N，代表有N組字詞 接下來

# 題目: Uva 820 - Internet Bandwidth # 題目說明 求S到T的最大流量 INPUT: 每筆測資第一行輸入一個整數N，代表node的數量 第二行輸入三個整數S、T、C 接下來有C行，每行有三個整數u、v、w，代表u連到v，capacity為w 當N為0時結束程式 OUTPUT: 輸出S到T的最大流量 # 解題方法 此題的解題概念為Maximum flow、Ford Fulkerson 先建表，按題目要求存為雙向 接著跑Ford Fulkerson，每次用dfs找到一條S到T的路徑 並記錄其中最小的capacity，直到無法找到一條S到T的路徑為止 將這些c

# 題目: UVa 10534 - Wavio Sequence # 題目說明 給一個長度為n的整數序列，求此序列的LIS與LDS相連最長為多少 LIS的結尾與LDS的開頭為同一個字 LIS的長度與LDS相同 INPUT: 每筆測資輸入一個整數n，代表序列長度 接下來輸入n個整數 OUTPUT: 輸出相同長度且相連的最大LIS與LDS的合 # 解題方法 若使用普通DP的方式找LIS與LDS會超時，所以使用greedy algorithm加速 分別找出LIS與LDS與每個元素的位置 ( LDS的找法為反向做LIS ) 之後設一個t從LIS與LDS中比較小的開始尋找 若LIS與LDS中的元

# 題目: UVa 11517 - Exact Change # 題目說明 給一個price與N個面額，求這些面額加總最接近price (大於等於) 的值與面額數量 INPUT: 第一行輸入一個整數T，代表測資數 每筆測資輸入兩個整數price與N 接下來有N個整數，代表面額 OUTPUT: 輸出面額加總最接近price (大於等於) 的值與面額數量 # 解題方法 此題為Coin Change問題 以一個sum來判斷最少需要做到多少，也就是所有大於sum的面額及加總都忽略 轉移方程為dp[j] = min(dp[j], dp[j - coin[i]] + 1) 代表sum為j