在這篇筆記中，會把之前幾篇講過的定理都串連起來，並且說明他們都是等價的。這些定理會有這些關聯不僅僅是因為我們在證明時使用了其他定理來證明，更是因為他們都可以用轉換成網路流量圖，再用最大流-最小割定理來證明。要看懂這篇筆記，需要的先備知識都寫在我的筆記裡了，可以去翻翻看 前情提要 : 匹配與霍爾定理、Kőnig 定理、連通性與 Menger 定理、最大流量-最小割定理 Menger 定理與最大流-最小割定理 最大流量-最小割定理遠比演算法書中寫的強大，這節來好好講一下最大流量-最小割定理可以如何來搞定 Menger 定理的第二部分，讓各位體會一下此定理的強大之處 除此之外，寫這段還有一個原因，流量網路中所定義的「割」與 Menger 定理定義的「割」，其實不是同一個東西，但網路上的大家 (包括我學校的競程團隊) 都喜歡混著用。這導致我當時在學最大流最小割定理時超級困惑，常常在想「為什麼明明一張沒權重的圖突然就有容量了，真的超級怪」所以這邊多一些廢話來證這個東西 用最大流-最小割定理證 Menger 定理

這份筆記是寫給初學者，原本目的是為了供內湖高中 AI 專班(資訊班)的學生認識競賽型程式，但是因為 ShanC 現在學太多這些有的沒的東西，所以就寫起來做個紀錄，內容有很多來自筆者的自言自語，供網上的各位參考 筆記搭配 CSES 、高中生程式解題系統 Zerojudge、AtCoder、Codeforces 等網站上的題目 為了配合競賽需求，因此可能會挑難一點的題目，請斟酌使用 作者：ShanC Discord: _shanc_ 如果有任何疑問歡迎私訊

這篇筆記會藉由 Ford-Fulkerson 演算法來聊聊最大流量-最小割定理。記得當初在修演算法課時聽老師說這是一個偉大的發現，我是覺得這定理真的很猛但沒那麼誇張啦。在介紹 Ford-Fulkerson 演算法之前，需要先介紹流量網路 (network flow)，一些性質與引理也順便聊聊 流量網路圖有許多不同的應用，像是現實中可以把水管當作邊，水管交界處用節點，這樣就可以表示成一張流量網路的圖。其他像是公路、電路跟網路傳輸等等都可以用網路流量的圖來建模。如果要說比較抽象的問題，像是二分圖最大匹配問題、二分圖最大點覆蓋問題、最小邊割問題等等都可以用流量網路來轉換 流量網路 Network Flow 網路圖 Network 一張路網圖 $N$ 是一張有向圖，其中 : 存在一個源點 (source vertex) $s$

雖然這篇被歸類在網路流量問題之中，但是為了銜接下一篇最大流量-最小割定理，我會暫時離題並討論一下什麼是「割 (cut)」。一般討論割的目的是為了瞭解一張圖 (graph) 是否足夠穩固，或至少要移除多少節點或邊才能使整張圖分為兩個連通塊 (component)。可以想像要是在一個公路的路網，被摧毀幾條公路就會使兩地之間無法溝通。顯然這是一個很重要的問題 本篇會來介紹點割 (vertex cut)、邊割 (edge cut) 與連通性 (connectivity)。最後會來介紹 Menger 定理，說明點割、邊割與路徑乃至於整張圖的關係。Menger 定理在圖論是個極為重要的存在，因為它的效力與許多不同的定理等價，像是 Hall 定理、 Kőnig 定理等都能使用 Menger 定理互相推出來 點割 Vertex Cut 定義 在一張圖 $G$ 中，若存在集合 $S\subseteq V(G)$ 使 $G-S$ 有多於一個連通塊，則 $S$ 是一個點割 (vertex cut) 給定 $x, y\in V(G)$，若存在集合 $S\subseteq V(G) - {x, y}$ 使 $G-S$ 沒有從 $x$ 到 $y$ 的路徑，則 $S$ 被稱為 $x, y$ 點割 ($x, y$-cut) $\kappa(x, y)$ 為最小 $S$ 的元素個數，即最小 $x, y$-cut 的大小

競程常出現的 flow 題當中，二分圖配對問題是常客中的常客，我猜原因是因為這樣子出題會比較隱晦一點，不容易看出可以 flow (或許吧)。 對於通靈專家而言，要把問題弄成二分圖匹配的樣貌並沒有什麼大不了的，但是對於一般人而言，這東西是非常難理解的，就算搞懂也很難理解建圖的過程，因此在本篇中我們需要先理解二分圖匹配問題的本質。其次需要知道許多問題背後可以轉化的原因是什麼，這會在下一篇解釋清楚 匹配 Matching 引入情境 今天有一群人要出去玩。已知飯店的每個房間只有兩個床位，且每一個人都只能挑一個床位。這群人的關係網如左圖，連邊的兩個人代表互相認識，他們希望可以跟自己認識的人同一個房間。如何分配才能使邊數最大呢? 下面的右圖或許是一種分法

Dijkstra 演算法是一個尋找最短路徑的演算法，可以對一張沒有負權邊的有向圖找出從原點到其他所有點的最短路徑距離 引入情境 假設位於台北市的你今天想從內湖高中騎車到捷運中山站附近吃拉麵，在每個路口都有幾條路任君挑選，你的 GPS 要如何找到最短路徑呢? Google 地圖上建議的路線 其中一種方法就是列舉每條路，把每條路的距離都加起來，然後選其中一條加起來最小的路線。這種方法可以找到最短路徑，卻要花上許多時間去列舉，甚至也有可能列舉到一些不值得考慮的路線，比如說從內湖到花蓮再南迴騎回來。顯然地，有些選擇荒謬至極 因此我們會需要有效率的 Dijkstra 演算法來幫助我們解決這個問題

藉由基礎圖論(一)，我們基礎的認識了圖的結構與一些有趣的圖。本章來聊聊圖的一些連通及一些有趣的性質 有一些名詞定義可能會因為不同作者而有不同說法，本篇筆記會以 D.B.West 寫的 Introduction to Graph Theory 2/e 為主 走訪一張圖 行走 Walk 假設在一張圖上，我們可以隨便走，然後將走過的節點與邊都記錄下來，那應該會得到一個序列 $v_0, e_1, v_1, ..., e_k, v_k$，那麼這個序列我們就稱之為一條「行走」 舉例: 下圖中，存在一行走 $v_1, ~e_2, ~v_2, ~e_5, ~v_3, ~e_6, ~v_1, ~e_1, ~v_2, ~e_2, ~v_1$ 由例子會發現，行走是允許重複的。

什麼是競程? 競程就是競技程式的縮寫，英文則是 competitive programming，簡稱 CP。算是資訊領域的分支，亦是有趣的學生活動之一。這領域近年來越來越熱門，對於升大學、考研究所、找工作都很有幫助，然而大多數人在資料結構與演算法相關課程看到一些基本的題目，就被嚇到而不敢跳進這個領域 參與競程你會需要... 程式能力: C/C++ (八成)、Python (or Java) 熟悉演算法: 二分搜尋、greedy、暴搜、dp、分治法、... 熟悉資料結構: 線段樹、樹狀陣列(數組)、雜湊表、字串(還有他的演算法)、... 數學能力: 數論(取mod)、排列組合、位元運算、高中幾何、線性代數(向量)、圖論 英文閱讀能力: 大學才要用到，因為題目都是英文

Fenwick Tree 又稱 Binary Indexed Tree(樹狀數組)，以下簡稱 BIT，是一個方便解決區間與前綴和問題的資料結構。本篇筆記會介紹其原理，也會說明此資料結構在題目上如何應用 Fenwick Tree 簡介 為什麼需要 Fenwick Tree? 給一個經典的問題: 「給定一個長度為 $n$ 的數列 $a_i$ ($1\leq i \leq n$)，即 $q$ 比詢問，每筆詢問給定 $l, r$，求區間 $[l, ~r]$ 的總和」這個問題非常基本，定義一個前綴和陣列 $pre_i=\sum_{j=1}^i a_j$，並預處理之，再使用差分 $pre_r - pre_{l - 1}$，即可算出 $a_l + a_{l+1} + ... +a_r$ Zerojudge e346. 區間和練習實作如下: // 以上略 int n, q, l, r;

擴充路徑演算法是一個找二分圖匹配的算法，可以無向的 $X, Y$- 二分圖進行 $X$ 與 $Y$ 的匹配，同時也可以用演算法的方式，將 Kőnig 定理證出來 有些人會將此演算法與匈牙利演算法搞混，所以特別需要說明一下，匈牙利演算法是使用矩陣尋找二分圖最大權完美匹配，而擴充路徑演算法則是使用單純的連邊關係，反覆迭代跑 DFS 或 BFS 來完成二分圖最大基數匹配。兩者的時間複雜度也有差異，匈牙利演算法的時間為 $O(n^3)$，而擴充路徑演算法則是 $O(mn)$ 似乎也有人將擴充路徑演算法稱作 Kuhn's algorithm 如果想完全理解本篇內容，可以閱讀前面的章節匹配與霍爾定理、Kőnig 定理 擴充路徑演算法 Augmenting Path Algorithm 擴充路徑演算法顧名思義需要使用擴充路徑 (又稱為增廣路徑) 的性質，也就是透過其定義中的「兩終點都是未匹配點」來尋找新的匹配

匈牙利演算法又稱 Kuhn-Munkres 演算法 (簡稱 KM) 是用於尋找二分圖最大權匹配。在打競程時，不常遇到這類題目，就算遇到也算是很好發揮，把問題轉化再套模板即可。然而，其原理卻相當複雜，理解原理後也有利於理解如何轉化匹配類型的題目，因此這篇會把整套原理說明清楚 閱讀之前可以先看前篇三篇匹配與霍爾定理、Kőnig 定理、擴充路徑演算法，有利於了掌握匹配問題的脈絡 最小權點覆蓋 Minimum Weighted Cover 情境 1 有一個農業公司擁有 $n$ 塊玉米田與 $n$ 個加工廠。每一塊田地可以生產的玉米產量各有不同，每一個加工廠的產能也不同。從第 $i$ 塊田地運送到第 $j$ 個加工廠可以賺到 $w_{i,j}$ 元。公司想要找一組好的匹配使獲利最大化 我們可以把他們的關係化成二分圖，田地 $X={x_1, x_2, ..., x_n}$、加工廠 $Y={y_1, y_2,...,y_n}$，將獲利 $w_{i, j}$ 作為權重擺在邊 $x_i~y_j$ 上，這問題就會轉化成二分圖最大權匹配問題

Kőnig 定理就是將二分圖 (bipartite graph) 最大匹配與最小點覆蓋串來起來的關鍵。由於二分圖最大匹配問題可以被歸約 (reduce) 成最大網路流量問題，因此最大網路流量問題也可以歸約成最小點覆蓋問題 建議先讀完另一篇筆記匹配與霍爾定理再來看這篇，因本篇會使用到霍爾定理的結論來證明 注: Kőnig's theorem 是由 Dénes Kőnig 與 Jenő Egerváry 於 1931 年證出來。許多資料經常將 Kőnig 以德文讀音譯作「柯尼希」，但是用匈牙利語的讀音是「柯尼格」。由於生活的時代背景是有包含奧匈帝國時期 ，許多研究也是以德文發表。因不知他祖上究竟是德裔還是匈牙利裔，亦或是德奧邊境的少數民族 (猜測是從德奧邊境地區到匈牙利)，我不敢貿然翻譯它的名稱 (但我比較傾向「柯尼格」這個翻譯)。Dénes Kőnig 其實是位匈牙利猶太人，致力於研究圖論與集合論，是現代圖論領域重要的發跡者(以往的圖論都散布在各個領域)。最後他在 1944 年因德國迫害而自盡 點覆蓋 Vertex Cover 一張圖 $G=(V,E)$ 的點覆蓋是一個集合 $Q\subseteq V(G)$ 使得包含所有邊的最少一個終點。我們會說 $Q$ 覆蓋 $E(G)$ $~$

拓樸排序是一種幫一張圖上的節點做線性排序的演算法。對於一張有向無環圖中的所有節點 $V(G) = {v_1,v_2,...,v_{|V|}}$，排出一個序列，使所有有向邊 $(u,v) \in E(G)$ 在序列中 $u$ 必排在 $v$ 之前 為什麼需要拓樸排序? 為什麼會需要這個演算法呢? 可以考慮以下問題: 引入情境 :::info 已知資工系有 $10$ 門課程: 課程 1

圖論是一門專門研究圖的數學領域，不管在路網規劃、網路流的運算或是作業研究等等的問題上都有非常多應用。在電腦科學上，圖論不管在什麼子領域幾乎都會出現。當然，圖論問題在競賽型程式上也是常客，有時常搭配其他的概念一起出題，說實話還挺討厭的。但是，如果從數學的角度出發的話，就會發現有很多概念很值得深入研究。 本篇主要是要從偏理論的角度出發，帶同學認識圖論的種種基本知識。 什麼是一張圖? 這問題還得從一個18世紀的問題說起-柯尼斯堡七橋問題。柯尼斯堡位於現今的俄羅斯境內，但是在18世紀時，還算是在東普魯士的領土。這座城市很神奇，有一條普列戈利亞河將土地切成好幾塊，有七座橋(現今有些被毀掉了，但那不是重點)連接各土地，長以下這副德行: 圖源: 維基百科 那時的一個知名數學家歐拉(其他翻譯: 尤拉)就在想一個問題: 「是否可以每個橋梁都走遍，但是每座橋只能走一遍?」藉由著個問題，歐拉畫出了數學史上第一張圖(graph)，並且透過這個模型證明了這問是不可能的，因此就誕生了圖的定義。

三分搜尋法基本上不常用，但是每次用到時都會令人驚艷 ||(驚嚇)|| 為什麼需要用到三分搜尋法 我們在二分搜尋法學過如何尋找具有單調性的資料。然而，當資料不具有單調性，我們勢必需要換一種方法來搜尋 單調性 單調性就是對於一個函數 $f(x)$: 「當 $x$ 越大 $f(x)$ 也會越大」 或者 「當 $x$ 越大 $f(x)$ 也會越小」 圖源: https://manabitimes.jp/math/1289

如何在一堆東西裡面尋找我想要的東西呢?相向大家都有相似的疑問吧? 這章節會介紹兩個常用的搜尋演算法 線性搜尋法 Linear Search 找東西最直觀的方法就是把所有東西掃過一遍，這樣就可以找到想要的內容了 而這種方法就叫做線性搜尋法 線性搜尋法很簡單，對於一個陣列，只需要一個一個比較是否相同即可 int arr[7] = {1, 4, 8, 13, 42, 89, 101}; int target = 42; // 目標值

這篇來講講實用的輸入以及輸出技巧。由於很多輸入輸出都跟使用的資料型態有關，所以也會帶到一點資料型態的部分 常用資料型態的輸入輸出 整數 資料大小範圍 資料型態 範圍 估計值 int

C語言程式設計導論 資料型態與輸入輸出 Table of Content 認識資料型態 資料型態的種類 資料型態的宣告 輸入與輸出 例題練習

C程式設計導論講義 這筆記是寫給初學者的講義，目的是為了供內湖高中AI專班(資訊班)的學生參考之學術用途，亦供網上的各位參考。內容有很多來自筆者的自言自語，請見諒。 講義搭配高中生解題系統 Zerojudge習題 為了銜接競賽需求，因此可能會挑難一點的題目，請斟酌使用。 作者：陳上恩 ShanC Discord: _shanc_ Gmail: shane931113@gmail.com

當我們在評估一個一段 code 的品質，時間與使用空間是一個很好的評估標準。好的 code 可以在較短的時間內達成任務，而比較差的則會花比較多時間。 然而，在不同時間、不同電腦環境下，程式執行起來的時間一定會有所差別。假設今天在兩組不同的 code 分別在不同的電腦執行相同任務，那們我們測出來的時間勢必會受到環境的影響。就算是在同一台電腦，也會因為時間點不同而產生差異。因此無法準確以時間去估計 code 的品質。 因此我們只能回歸到程式碼本身的執行步驟來評估其品質 步驟數量分析 考慮以下程式碼片段 int a; // 宣告整數變數 a a = 5; // a 被賦值為 5 printf("%d", a); // 輸出 a