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

在一些路網的構建當中，我們時常期望可以找出一個最簡的路網，使資料可以互相傳遞，而且花費最小。要實現這樣的想法，就會用到最小生成樹的概念 生成樹 Spanning Tree 定義 若一棵樹 $T$ 是一張連通圖 $G$ 的子圖，且 $V(T) = V(G)$ (即 $T$ 擁有所有 $G$ 的節點)，則稱 $T$ 為一棵生成樹 右圖就是左圖的生成樹

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

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

快速冪是一個處理整數冪次的演算法，可以在 $O(log ~n)$ 的複雜度完成任務 一般來說我們處理冪次問題 $a^{~n}$ 會使用以下方法: int ans = 1; for(int i = 0; i < n; i++) ans *= a; cout << ans; 這種方法最直觀，但是卻需要 $O(n)$ 的時間才能完成 對於數字過大的數字實在太耗時 因此我們會需要用到快速冪來處理這個問題

樹是圖論中一種很常見的圖，在電腦科學中更是不可或缺的一種資料結構。由於其特殊性，相關應用也相當廣泛，是競程不可或缺的題型之一。很多人把樹當作是一門學問獨立出來稱作「樹論」，但嚴格上來說不能這樣稱呼，因為他就是一種特殊結構的圖而已，基本上出了中文競程圈就完全聽不到這種叫法 本文會介紹樹的定義、性質與用途 簡介 澄清 首先，資工的樹長下圖右邊的樣子 : 根在上、葉在下 ||別人覺得你畫這樣有病是正常的 XD|| 常見例子

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

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

接續最大流-最小割定理，本篇筆記會講講為什麼需要更好的演算法去找最大流量。總共會聊到兩種演算法 : Edmonds-Karp 演算法與 Dinic 演算法 競程會用的應該只有 Dinic 演算法而已，所以如果只想把這裡當速食店的話讀 Dinic 演算法那段就好 Ford-Fulkerson 演算法的問題 時間複雜度太大 (or 不確定) 在最大流-最小割定理中，有講到 Ford-Fulkerson 演算法，這是由 Ford 與 Fulkerson 在 1954 年提出。然而這演算法最大的問題就在於，其並沒有明確的說明要如何在圖中找出一條 $s$-$t$ 路徑，所以我們其實並不知道實作起來的複雜度為何。由於很多數學家不見得有時間複雜度的觀念，他們很多時候只會說明某某東西存在卻不說要怎麼找。演算法的時間複雜度在最差情況下恐怕會來到指數時間 (exponential running time)，當然這跟二進制的編碼長度也有關係。因定義不夠明確的緣故，Ford-Fulkerson 演算法有時候會被稱為「方法」而不是「演算法」 好的演算法? 那麼 Ford 與 Fulkerson 有提出演算法去解決算法的問題嗎? Fulkerson 算是有，只是用的是線性規劃 (Linear Programming) 的方法，詳情可以看這篇 paper。想知道線性規劃是什麼可以修修看作業研究 (Operation Research)，反正我是沒修過

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

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

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

雖然這篇被歸類在網路流量問題之中，但是為了銜接下一篇最大流量-最小割定理，我會暫時離題並討論一下什麼是「割 (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 的大小

藉由基礎圖論(一)，我們基礎的認識了圖的結構與一些有趣的圖。本章來聊聊圖的一些連通及一些有趣的性質 有一些名詞定義可能會因為不同作者而有不同說法，本篇筆記會以 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;

匈牙利演算法又稱 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)$ $~$

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

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