Advanced Competitive Programming

Presentation on theme: "Advanced Competitive Programming"— Presentation transcript:

1 Advanced Competitive Programming
國立成功大學ACM-ICPC程式競賽培訓隊 Department of Computer Science and Information Engineering National Cheng Kung University Tainan, Taiwan

2 Outline 最大流 Articulation point Strongly Connected Components

3 Maximum Flow 最大流

4 最大流 給定帶權重連通圖 找到此圖從 s 點 到 t 點的最大流量

5 前提 流 流量 容量 剩餘容量

6 前提 流 流量 容量 剩餘容量

7 流 s t

8 流 s t

9 流 s t

10 流 s t

11 流 s t

12 前提 流量 容量 剩餘容量

13 流量 s t

14 2 流量 s t

15 1 流量 (不必多) s t

16 9 流量 s t

17 1 流量 s 2 1 t

18 前提 流量 容量 剩餘容量

19 容量 2 1 s 1 2 1 1 2 t

20 流量/容量 0/2 0/1 s 0/1 0/2 0/1 0/1 0/2 t

21 x/y x := 流量 y := 容量

22 2 流量/容量 2/2 0/1 s 0/1 2/2 0/1 0/1 2/2 t

23 1 流量/容量 1/2 0/1 s 0/1 1/2 0/1 0/1 1/2 t

24 2 流量/容量 1/2 0/1 s 1/1 1/2 0/1 1/1 2/2 t

25 前提 流量 容量 剩餘容量

26 x/y x := 流量 y := 容量 y-x = 剩餘容量

27 2 流量/容量 1/2 0/1 s 1/1 1/2 0/1 1/1 2/2 t

28 2 剩餘容量 1 0/1 s 1 0/1 t

29 2 剩餘容量 1 0/1 s 1 0/1 t

30 2 剩餘容量 1 0/1 s 0/1 t

31 2 剩餘容量 1 0/1 s 0/1 t

32 2 剩餘容量 1 1 s 1 t

33 2 Augmenting path 1 1 s 1 t

34 2 流量: 1 1 1 s 1 1 t

35 3 剩餘容量 s 1 t

36 3 剩餘容量 1 s t

37 最大流 給定帶權重連通圖 找到此圖從 s 點 到 t 點的最大流量

38 最大流 給定帶權重連通圖 找到此圖從 s 點 到 t 點的最大流量 剛剛的例子，最大流就是 3

39 找出最大流 Augmenting path Ford-Fulkerson method Edmonds-Karp algorithm

40 找出最大流 Augmenting path Ford-Fulkerson method Edmonds-Karp algorithm

41 Augmenting path 指的是一條路徑 它的剩餘容量 足夠讓大於 0 的流量通過

42 s t

43 F1 s t

44 F2 s t

45 F1 = F2 s t

46 F1 > F2 s t

47 F1 < F2 s t

48 具體來看 1 3 3 3 s 3 t 3 3

49 3 F1 3 1 s t

50 3 F2 3 1 s t 1 1

51 流不過去 因為沒有剩餘容量了!!

52 流不過去 因為沒有剩餘容量了!! 怎麼辦?

53 3 F1 過後，剩餘容量 3 1 s t

54 3 F1 過後，剩餘容量 1 s t

55 3 F1 過後，剩餘容量 1 s t

56 流不過去 因為沒有剩餘容量了!! 怎麼辦?

57 流不過去 因為沒有剩餘容量了!! 怎麼辦? 為了 F2 ，也給他一個剩餘容量

58 3 剩餘容量 1 s t

59 3 剩餘容量 3 1 s t

60 3 剩餘容量 3 1 s t

61 流得過去!! 跟水流一樣

62 流得過去!! 跟水流一樣 如果第二條水流更強，就有機會壓過第一條水流

63 流得過去!! 跟水流一樣 如果第二條水流更強，就有機會壓過第一條水流 給他剩餘容量，就是給流向逆轉的機會 跟八卦版很像，偶爾也會出現風向逆轉的傾向

64 3 剩餘容量 3 1 s t

65 4 F2 1 3 3 s 3 t 3 3 3

66 4 剩餘容量 3 2 s t

67 與 F1 同樣 給下一條流機會 所以反向邊都得給予同等的剩餘容量 流量多少就給多少

68 4 剩餘容量 3 2 s t

69 4 剩餘容量 3 2 1 s 1 t

70 Augmenting path 指的是一條路徑 它的剩餘容量 足夠讓大於 0 的流量通過 顯然已經找不到這條路徑了 故原圖的最大流為 4

71 兩個流 實際上相抵之後 F1 比 F2 來得大， 所以在中間相遇部分會有 F3 = F1 - F2

72 剩餘容量 1 3 3 3 s 3 t 3 3

73 4 流量圖 (權重是流量) 3 2 1 s t

74 4 三條流 s t

75 找出最大流 Augmenting path Ford-Fulkerson method Edmonds-Karp algorithm

76 Ford-Fulkerson method
可以討論如何找到最大流了! 直覺的，對於存在 augmenting path 的圖

77 Ford-Fulkerson method
可以討論如何找到最大流了! 直覺的，對於存在 augmenting path 的圖 給他流過去就對了!

78 Ford-Fulkerson method
可以討論如何找到最大流了! 直覺的，對於存在 augmenting path 的圖 給他流過去就對了! 流到不再能找到 augmenting path

79 Ford-Fulkerson method
可以討論如何找到最大流了! 直覺的，對於存在 augmenting path 的圖 給他流過去就對了! 流到不再能找到 augmenting path 也就是流量只能得到 0

80 找出最大流 Augmenting path Ford-Fulkerson method Edmonds-Karp algorithm

81 Edmonds-Karp algorithm
如何找到 augmenting path?

82 Edmonds-Karp algorithm
如何找到 augmenting path? Edmonds-Karp 用 BFS

83 Edmonds-Karp algorithm
如何找到 augmenting path? Edmonds-Karp 用 BFS 每當剩餘容量 >0 路徑就能延伸

84 Edmonds-Karp algorithm
如何找到 augmenting path? Edmonds-Karp 用 BFS 每當剩餘容量 >0 路徑就能延伸 原則就是幹你娘流爆 效仿 Ford-Fulkerson method 跟產薯條的原則類似

85 實作 int max_flow = 0;

86 實作 while (1) { : . if (flow[t] == 0) break; }

87 實作 memset(vis, false, sizeof(vis)); vis[s] = true; memset(flow, 0, sizeof(flow)); flow[s] = INF; queue<int> Q; Q.push(s);

88 實作 while (!Q.empty()) { int u = Q.front(); Q.pop(); for (int v = s; v <= t; v++) { if (!R[u][v] || vis[v]) continue; vis[v] = true; Q.push(v); pre[v] = u; // 紀錄 augmenting path flow[v] = min(flow[u], R[u][v]); // 流只挑最小的剩餘容量 } }

89 實作 max_flow += flow[t]; for (int v = t, u; v != s; v = u) { u = pre[v]; R[u][v] -= flow[t]; R[v][u] += flow[t]; }

90 Questions?

91 練習 UVa OJ 820 Internet Bandwidth

92 Articulation Point 關節點

93 比較有向圖與無向圖「兩點間的關係」 無向圖： 有向圖： 連通 Connected：兩點之間邊邊相連
強連通 Strongly Connected：兩點之間雙向皆有路可通

94 使用 Tree 的角度觀察 Graph 一張圖裡面可以有數個「連通塊」(Connected Component)
連通塊可以使用 DFS、BFS 來「遍歷」 連通塊被「遍歷」，形成一棵樹 (遍歷是不重複拜訪點  無環連通圖  樹) 原本圖上的邊就分成 構成樹的邊(tree edges) 未使用的邊(other edges)

95 無向圖 使用 「DFS」 遍歷 請問使用 DFS 時 other edge 必定只會連到直系祖先？ other edge tree edge
圖片來源：演算法筆記「Articulation Vertex Bridge」

96 無向圖 使用 「DFS」 遍歷 other edge 必定只會連到直系祖先！ 因為 DFS 的特性，反證法 重新命名  back edge
tree edge 圖片來源：演算法筆記「Articulation Vertex Bridge」

97 無向圖 使用 「DFS」 遍歷 如果有不是連接到直系祖先的 edge ，那為什麼 DFS 的時候，這個邊不是 tree edge？
back edge tree edge 圖片來源：演算法筆記「Articulation Vertex Bridge」

98 Articulation Point (AP)
對於一個連通圖(圖中所有點在同個連通塊中) 如果此點被移除後，會導致連通圖不再連通。 稱此點為 Articulation Point

99 觀察 Articulation Point (AP)
考慮一個連通圖。 如果移除 point7 ，還是不是連通圖？否 如果移除 point11，還是不是連通圖？是 如果移除 point16，還是不是連通圖？是 圖片來源：Wikipedia「Biconnected component」

100 觀察 Articulation Point (AP)
考慮一個 tree(無環連通圖) 如果移除 pointA，還是不是連通圖？否 如果移除 pointB，還是不是連通圖？否 如果移除 pointE，還是不是連通圖？是

101 觀察 Articulation Point (AP)
考慮一個 tree (無環連通圖) 如果移除 pointA，還是不是連通圖？是

102 Tree 上的 AP 對於任一 Node： num(parent) + num(child) < 2  不是 AP (斷掉只會斷自己) Ex: 葉  (1+0)  不是 AP num(parent) + num(child) ≧ 2  是 AP (斷掉會斷別人) Ex: 莖  (1+x)  是 AP

103 從 tree 到 graph 對於一張圖加上邊 有機會讓 「非AP」 變成 「AP」 嗎？ 否

104 使用 DFS tree 的角度找 AP 把「圖」經由遍歷得到「帶有 back edge 的 tree」
「back edge」有機會讓 「AP」 變成 「非AP」

105 觀察 Back edge 所帶來的影響 如果移除 point0，還是不是連通圖？否 如果移除 point1，還是不是連通圖？否
tree edge back edge 圖片來源：演算法筆記「Articulation Vertex Bridge」 如果移除 point0，還是不是連通圖？否 如果移除 point1，還是不是連通圖？否 如果移除 point3，還是不是連通圖？是

106 觀察 Back edge 所帶來的影響 「此 node 的任意孩子」 無法藉由 back edge 走到更高的位置
tree edge back edge 圖片來源：演算法筆記「Articulation Vertex Bridge」 「此 node 的任意孩子」 無法藉由 back edge 走到更高的位置 那 node 被拔掉會造成連通圖斷掉 此 node 是 AP 這裡的「高」，是取決於 DFS tree 的深度。

107 題目練習 UVa 315 Network 在一個網路建案中，想要請你找出幾個關鍵的點， 一旦死掉會導致網路不連通。 解答

108 討論 low 值 的更新方式 每次的「循邊」都需要維護 low 值 那為什麼這邊不能用 low[v] 取代 dep[v]？ 備註：
這是上頁投影片中 uva 315 的解答程式碼。 dep(n) 代表節點 n 的 depth low(n) 代表節點 n 透過 back edge 能連向最高節點的 depth 值

109 討論 low 值 的更新方式 考慮以下例子： 請問這個點是不是 AP ？ 是 其正下方的子孫所能觸及的最高點到達不了 root。
所以 low 不可以上去之後下來再藉由其他 back edge 上去！

110 Strongly Connected Component
有向圖的強連通元件

111 比較有向圖與無向圖「兩點間的關係」 無向圖： 有向圖： 連通 Connected：兩點之間邊邊相連
強連通 Strongly Connected：兩點之間雙向皆有路可通

112 Strongly Connected Component
考慮一個有向圖中的點集合構成的「子圖」，且集 合中任兩點之間須滿足強連通關係，則稱這個極大 點集合為一個強連通元件。 Ex: {5,6,7}、{2} 兩組都是 SCC 圖片來源：演算法筆記「Articulation Vertex Bridge」

113 使用 Tree 的角度觀察 Graph 一張圖裡面可以有數個「連通塊」(Connected Component)
連通塊可以使用 DFS、BFS 來「遍歷」 連通塊被「遍歷」，形成一棵樹 (遍歷是不重複拜訪點  無環連通圖  樹) 原本圖上的邊就分成 構成樹的邊(tree edges) 未使用的邊(other edges)

114 有向圖 使用 「DFS」 遍歷 請問使用 DFS 時 other edge 必定只會連到直系祖先？ other edge tree edge
圖片來源：演算法筆記「Articulation Vertex Bridge」

115 有向圖 使用 「DFS」 遍歷 other edge 有可能: Back edge Forward edge Cross edge
tree edge other edge 圖片來源：演算法筆記「Articulation Vertex Bridge」

116 有向圖 使用 「DFS」 遍歷 other edge 有可能: Back edge Forward edge Cross edge
tree edge forward edge 圖片來源：演算法筆記「Articulation Vertex Bridge」

117 有向圖 使用 「DFS」 遍歷 other edge 有可能: Back edge Forward edge Cross edge
tree edge cross edge 圖片來源：演算法筆記「Articulation Vertex Bridge」

118 有向圖 使用 「DFS」 遍歷 other edge 有可能: Back edge Forward edge Cross edge
tree edge back edge 圖片來源：演算法筆記「Articulation Vertex Bridge」

119 Tarjan Algorithm 形成 SCC 的條件為 SCC 內任兩點 a → b 且 b → a  形成有向環

120 時間不多直接說結論 Tree 無環 Back edge 才可能把 dfs tree 連接成有向環。 剩下兩種 edge 不用考慮。

121 SCC 與 back edge 「同一個 SCC 上的點」 藉由 back edge 走到「同個」高的位置
這裡的「高」，是取決於 DFS tree 的深度。 Ex: Point6, Point7, Point5 的 low值 都會等於 dfn(Point 6) 備註：因為這裡需要確定最高的是哪個點，所以這裡使用 dfn(n) 取代 dep(n)。 dfn(n)為 dfs 的順序，同樣有深度的感覺。

122 題目練習 ICPC LA 4262 - Road Networks
找出 SCC。 解答