題目： UVa - 11380 - Down Went The Titanic 題目說明 給定一個圖，上面有薄冰 ‘.’ 或 ‘*‘, 厚冰 ‘@’, 木塊 ‘#’，一開始人都在 ‘*‘ 上，薄冰只能走一次就會沉掉，厚冰次數不限，如果人走到木塊上就獲救了，但是一個木塊的容量只有 p，求最多能有多少人獲救。 UVA 11380 - Down Went The Titanic（网络流）_Remilia’s-CSDN博客 解題思路最大流，依照上面的說明建邊後使用 Dinic 求解即可。 參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120 ...

題目： UVa - 10330 - Power Transmission 題目說明基哥上課講過了。 解題思路最大流，可使用 Dinic 求解。 參考解法...

課程名稱：演算法概論 CS309 B授課教師：林基成發放時間：2021-04-24截止時間：2021-05-03 題目說明這次的作業是 UVa 中的 3 題題目，與 Maximum Flow 有關。 UVa 820 - Internet Bandwidth：UVa - 820 解題紀錄 UVa 11418 - Clever Naming Patterns：UVa - 11418 解題紀錄 UVa 12873 - The Programmers：UVa - 12873 解題紀錄

題目： UVa - 12873 - The Programmers 題目說明 給 P 個隊伍、S 個賽區，每隊分別都有可以去的賽區，而每一個賽區最多容納 C 個隊伍。請問參加的總隊伍數量最大為何？ UVa 12873 - The Programmers | Morris’ Blog 解題思路最大流，可使用 Edmonds-Karp 求解，也可使用 Dinic。這題使用 Edmonds-Karp 執行時間會非常久，但還是可以過，建議使用 Dinic。 將每個隊伍及賽區各自視為一個點，從源點連到隊伍再連到賽區最後連到匯點，之後最大流求解即可。 參考解法Edmonds-Karp: 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051 ...

題目： UVa - 11418 - Clever Naming Patterns 題目說明 給一系列詞組，僅從每組中按字母表順序取一個詞，比如有這三個組：Dog Cat BigBetterAnswer Call需要取 3 個詞，A, B, C, 開頭，每組取一詞。第二組的 B 必須用上，第三組的 A 必須用上，剩餘的第一組就必須取 Cat 了：AnswerBetterCat 请教‌‌‌‌‍‍‌‍‌‌‍‍‍‌‌‍‍‍‍‍‍‌‌‌‍‌‍‌‌‌‍‌一下我这个解法怎么不对了–UVa 11418 Clever Naming Patterns 這個說明不是很好理解，可是我也懶得寫。 解題思路最大流，可使用 Edmonds-Karp 求解，也可使用 Dinic。 將每組詞組當作一個點，每個出現的詞也當作一個點，A ~ Z 各為一個點，從源點連到詞組再連到詞，再連到詞的第一個字母，最後流到匯點，之後最大流求解即可。 參考解法Edmonds-Karp ( 將一開始的 Capacity 當作 Residual Network ) : 12345678910111213141516171819202122 ...

題目： UVa - 820 - Internet Bandwidth 題目說明 求 S 到 T 的最大流量為多少。網路是雙向連接的，但共用頻寬，例如 A B 10，則 A 到 B 的流量 + B 到 A 的流量要小於等於 10。另外這題給測資的方式會有可能給你很多組 A B Xi，所以 A 到 B 的頻寬要把 Xi 全部加起來，例如底下例子 1 ~ 2 的頻寬為 30。21 2 21 2 101 2 20 Programming學習筆記: UVa 820 Network Bandwidth 解題思路最大流基本題，可使用 Edmonds-Karp 求解，也可使用 Dinic。 參考解法Edmonds-Karp: 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991 ...

題目： UVa - 10534 - Wavio Sequence 題目說明 給定一個長度為 n 的整數序列，求一個最長子序列（不一定為連續），使得該序列的長度為奇數 2 * k + 1，前 k + 1 個數嚴格遞增，後 k + 1 個數嚴格遞減。（嚴格遞增 / 遞減意味著相鄰兩個數不能相同） UVA 10534 - Wavio Sequence LIS_C++入門知識 解題思路遞增的部分很明顯是 LIS，遞減的部分可以視為反向的 LIS，先做出正向及反向的 LIS，之後遍歷陣列，遍歷到的元素視為中心，可以組出的長度為正向及反向 LIS 的較小值乘 2 加 1 ( 依照題目要求 )。 參考解法12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include <bits/stdc++.h>using namespace std;#define FOR(i ...

課程名稱：演算法概論 CS309 B授課教師：林基成發放時間：2021-04-04截止時間：2021-04-09 題目說明這次的作業是 UVa 中的 3 題題目，與 Dynamic Programming - Coin Change 有關。 UVa 357 - Let Me Count The Ways：UVa - 357 解題紀錄 UVa 10306 - e-Coins：UVa - 10306 解題紀錄 UVa 11517 - Exact Change：UVa - 11517 解題紀錄

題目： UVa - 11517 - Exact Change 題目說明Unfortunate狗的ACM園地: 11517 - Exact Change 解題思路DP 的 Coin Change 問題，核心概念為枚舉每一個最後加入的面額。需要注意的是一種面額只能使用一次，因此做的時候要從後面往前做，避免同種金額使用多次。 參考解法1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include <bits/stdc++.h>using namespace std;// reference: https://ppt.cc/fp0yAxstatic auto __ = []{ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0;}();const int INF = (i ...

題目： UVa - 10306 - e-Coins 題目說明Unfortunate狗的ACM園地: 10306 - e-Coins 解題思路DP 的 Coin Change 問題，核心概念為枚舉每一個最後加入的面額。...