前置定義

對于一個圖 \((V, E)\) 和它的一個匹配 \(M\)，存在著如下兩種簡單路徑：

• 由非匹配，匹配邊交錯構成的簡單路徑為交錯路。

• 起點為非匹配點且終點也為非匹配點的交錯路為增廣路。

對于任何一個節點的子集 \(W \subseteq V\)，稱集合 \(N_G(W)\) 表示圖 \(G\) 中與 \(W\) 相鄰（相鄰指兩點間存在邊）的點構成的集合。

Berge 引理

Berge 引理：對于一個圖 \(G = (V, E)\) 和它的一個匹配 \(M\)，該匹配是最大匹配，當且僅當不存在增廣路。

先證明必要性：

反證法，若存在一個增廣路。
首先，因為增廣路是 \(非匹配邊 \to 匹配邊 \to \cdots \to 非匹配邊\) 這種形式的，所以長度必然是奇數。
所以可以得到這個路徑上非匹配邊的數量是匹配邊的數量 \(+1\)。
所以我們考慮翻轉整個路徑的狀態，即 \(匹配 \to 非匹配, 非匹配 \to 匹配\)。
容易發現此時的匹配是合法的，且匹配數比原來多了 \(1\)，與 \(M\) 是最大匹配矛盾。

然后考慮充分性：

同樣反證法，在不存在增廣路的前提下，若存在另外一個匹配 \(M'\) 使得 \(|M'| > M\)。
考慮對稱差新的匹配 \(M \oplus M'\)，即相同的邊將會抵消的運算。
在這個新圖 \((V, M \oplus M')\) 上，容易發現，每個點的度數只能是 \(0, 1, 2\)，所以對于這個新圖，其所有聯通塊，要么是一條鏈，要么是一個環。
容易發現一個性質，對于一個度數為 \(2\) 的點，其相鄰的邊必定是分別來自 \(M\) 和 \(M'\)；且在這個新圖上，不可能存在奇環；于是可以得到對于每個環，都是偶環，且 \(M\) 和 \(M'\) 中的邊出現次數一樣。
那么此時來考慮鏈，顯然肯定是由 \(M, M'\) 中的邊交替構成的，即構成交替路，對于 \(M'\) 中的邊，在 \(M\) 中是非匹配邊。
由于 \(|M'| > M\)，那么顯然必然會出現一個起點終點都是非匹配點的鏈，其是增廣路，與 \(M\) 不存在增廣路矛盾。

Hall 定理

對于一個二分圖 \((X, Y, E)(|X| \le |Y|)\)，若存在一個匹配 \(M\) 使得使得 \(X\) 中所有頂點都是匹配點，那么稱 \(M\) 是一個完美匹配。

Hall 定理：假設 \(G\) 是一個二分圖 \((X, Y, E)\)，存在一個完美匹配當且僅當對于所有 \(W \subseteq X\) 都滿足 \(|N_G(W)| \ge |W|\)。

先證明必要性：

若存在完美匹配，且存在 \(W\) 使得 \(|N_G(W)| < W\)，顯然這 \(|W|\) 點無法和少于它們點數的集合形成完美匹配，故矛盾。

然后考慮充要性：

考慮反證法，即對于所有 \(W \subseteq X\) 都滿足 \(|N_G(W)| \ge |W|\)，且存在一個點 \(u \in X\) 是非匹配點，由 Berge 引理得到，即無法找到一個從 \(u\) 出發的增廣路。
我們令 \(W\) 表示 \(u\) 走交錯路能到達的頂點集合，設 \(W\) 中左部點是 \(S\)，右部點是 \(T\)，由于從 \(u\) 必然是非匹配邊出發，則最后回到左部點時一定是匹配邊，即 \(S\) 中除了 \(u\) 都是匹配點；對于右部點，若存在一個點 \(v\) 是非匹配點，那么 \(u \to v\) 的交替路就是增廣路，矛盾，故 \(T\) 中也全是匹配點。
由于 \(S\) 中除了 \(u\) 與 \(T\) 都是通過邊相連的，又全是匹配點，于是兩兩一一對應，故 \(|S| - 1 = |T|\)；此時注意到必然有 \(T \subseteq N_G(S)\)，故 \(|T| \le |N_G(S)|\)；然后又可以發現 \(N_G(S)\) 中必然全是匹配點，因為如果存在非匹配點的話，可以從 \(u\) 開始走到那個非匹配點形成增廣路形成矛盾，于是可以得到 \(N_G(S) = T\)。
于是 \(|N_G(S)| = |T| < |S|\)，與初始條件矛盾。

推論 1：

一個任意二分圖 \((X, Y, E)(|X| \le |Y|)\)，其最大匹配數是 \(|X| - \max\limits_{W \subseteq X}(|W| - |N_G(W)|)\)。

考慮轉化為 \(\min\limits_{W \subseteq X}(|X| - |W| + |N_G(W)|)\)。

然后對于求最大匹配問題，可以進行網絡流的建模，然后跑最大流，也就是最小割，而上面式子的意義就是 \(|X| - |W|\) 是左邊割掉的點，\(|N_G(W)|\) 是右邊割掉的點，那么取 \(\min\) 就是最小割。

得證；當然這個還可以不用最小割來理解，感興趣的可以自己上網查一下。

例題

P3488 [POI 2009] LYZ-Ice Skates

發現只需要判斷是否存在完美匹配，于是考慮使用 Hall 定理。

此時發現 \(W \subseteq S\) 的情況太多了，但是你會發現，若 \(W = \{ a_1, \cdots, a_k\}\) 時，只需要 \(W = \{a_1, a_1 + 1, \cdots, a_{k}\}\) 滿足條件就必然滿足，于是只需要對于所有區間 \(W = [l, r]\)，滿足 \(|N_G(W)| \ge |W|\) 即可，即：

轉化一下：

于是只需要判斷 \((s_i - k)\) 的最大子段和是否大于 \(dk\) 即可。

于是問題轉化為單點加，全局最大子段和，使用線段樹維護即可，時間復雜度為 \(O(N \log N)\)。