11506: Angry Programmer ★★★★☆ 題組：Contest Set Archive with Online Judge

Presentation on theme: "11506: Angry Programmer ★★★★☆ 題組：Contest Set Archive with Online Judge"— Presentation transcript:

1 11506: Angry Programmer ★★★★☆ 題組：Contest Set Archive with Online Judge
解題者：朱峘愷 解題日期：2011年5月31日 題意：你是個因為沒完成任務而失業的工程師，為了報復老闆，你要搞破壞把他的電腦和central server中間的連結給切斷。計算出最少的損失。 Boss的電腦和central server之間會有數台電腦由線來連接起來。電腦之間最多只有一條線連接， 線為雙向的。除了老闆的電腦和server ，可以任意破壞電腦或線，每個都會有不同的損失 。

2 題意範例：

3 題意範例： 2 2 3 1 BOSS 1 SERVER 4 3 3 3 損失=1+3=4 5

4 解法：題目說的兩電腦之間連結並不只限於跟老闆的電腦或server連結。
損失=3+2=5

5 解法：首先，這事實上就是一張圖有s 、 t兩點，還有edge和vertex 還有他們拔掉需要的cost 。問題是要多少cost才能讓s到不了t 。
6 6

6 解法：如何去尋找有很多種方法，基本上要先把圖存入array裡面，然後再array裡面去search出最少的cost 。
以下提供幾種方法: 這題是minimum-cut problem 。 我們可以用Max-flow min-cut定理來處理 。 也就是最大流量跟容量最小的Cut是相等的。 所以我們就可以算maximum flow。

7 解法：介紹兩個計算maximum flow的方法
Ford-Fulkerson Algorithm Lester Randolph Ford, Jr. Delbert Ray Fulkerson 兩位美國數學家研究出來的 利用Residue network的觀點來找出Maxmium flow。 重複找Augmenting path(擴充路徑)直到找不到為止。 也就是剩餘網路上面一條由源點到匯點的路徑。 所有擴充路徑總合起來，就是最大流。 流量總和，就是最大流流量。 找了F條。 時間複雜度是O(E*F)。

8 解法：介紹兩個計算maximum flow的方法
Edmonds-Karp Algorithm Ford-Fulkerson Algorithm的進階版。 使用Breadth-first search(BFS)來找Augmenting path。 每次找擴充路徑的時候，以s到t的最短路徑作為擴充路徑 ，並且讓擴充的流量到達瓶頸。 可以避免浪費管線空間，而能較快找到最大流。 找VE次就可得到最大流。 BFS 的時間複雜度 O(V+E) ，省略了 V 寫成O(E) 。 總共是 O(E * VE) = O(V * E^2) 。 時間複雜度是O(V * E^2) 。

9 解法： BFS的運作 3+4+5=12 1 3/6 2/3 4 7 6 5

10 解法範例：無 討論：無