定義

對于一張二分圖 $G=(V,E)$，設其左右部點集分別為 $V_L,V_R$，不妨認為 $(|V_L|\le |V_R|)$，定義該二分圖的一組 完備匹配 為左部 $|V_L|$ 個點全部成為匹配點的匹配。

Hall 定理講的是，定義 $N(v)$ 為節點 $v$ 的鄰居集，如果對于任意 $S?V_L$，均有 $|S|\le |\underset{u\in S}{?}N(u)|$，則該二分圖存在一組完備匹配。

證明參考資料

一些推論

1. 對于一張 $k$ 正則二分圖（每個點度數都為 $k$，且 $k\ge 1$），若 $|V_L|=|V_R|$，則必有 $k$ 組邊 不交 的完美匹配。

   證明：考慮歸納，只需證明該二分圖存在一組完美匹配，那么刪去這些匹配邊后會得到 $k?1$ 正則二分圖，歸納即證。
   考慮 hall 定理，若存在 $S?V_L$ 使得 $|S|>|\underset{u\in S}{?}N(u)|$，由于 $|\underset{u\in S}{?}N(u)|$ 中的點的度數之和必定 $\ge$ $k|S|$，但該點集的點數卻小于 $|S|$，顯然矛盾，因此 hall 條件成立，存在完美匹配。

2. 左右兩部分別為 $V_L,V_R$ 的二分圖最大匹配為 $|V_L|?\underset{S?V_L}{\max }(|S|?|\underset{u\in S}{?}N(u)|)$。
   很好理解。

應用

題目類型很多。

直接應用

數據范圍比較小，可以 $2^n$ 枚舉集合 check 是否滿足 hall 條件

AT_arc106_e [ARC106E] Medals

枚舉集合完之后問題轉化成了：求多少天才能讓并集大小為 $K$。

試試二分，好像更好做了，但推式子還是推不出來答案。

然后觀察一下發現答案是 $2nk$ 級別的，是可以直接掃一遍的。

剩下就很簡單了。

?

數據結構維護 hall 條件

正常來說想使用 hall 來 求/判斷 最大匹配需要枚舉所有集合 $S$，復雜度不可接受

但在某些題目中合法（或者說有用）的 $S$ 可能會滿足某種性質（比如是一段區間），從而使得枚舉量大大減少，可以用數據結構直接維護。

P3488 [POI 2009] LYZ-Ice Skates

直接應用，顯然有用的人的集合一定是一段區間，推推式子就轉化成了最大子段和。

CF338E Optimize!

有用集合是值域上一段前綴。

AT_arc076_d [ARC076F] Exhausted?

以人為左部點列 hall 條件，求它們的并；可以看成先選出一段并區間，再選出盡可能多的人，這樣方便用數據結構維護。

求并可以轉化成求補集交，掃描線補集右端點，維護所有左端點答案。

P9528 [JOISC 2022] 螞蟻與方糖

如果不單單是判斷，而是求最大匹配會有什么變化呢？

發現區別在于：現在可能選出 多段 連續區間。

形式化的描述一下簡化后的問題：設螞蟻前綴和為 $S_i$，方糖前綴和為 $T_i$，你要選出若干段區間 { l 1 , r 1 , . . . l k , r k } \{l_1,r_1,...l_k,r_k\} {l1?,r1?,...lk?,rk?}，最大化 $\sum _{i=1}^k{T}_{r_i?L}?T_{l_i+L?1}?(S_{r_i}?S_{l_i?1})$ 最大。

化一下式子：$\sum _{i=1}^k(T_{r_i?L}?S_{r_i})+(S_{l_i?1}?T_{l_i+L?1})$

令 $P_i=T_{i?L}?S_i$，$Q_i=S_i?T_{i+L}$，那么就是每個點有權值 $P,Q$，要選出形如 $QPQP...QP$ 的若干個點，最大化選出點的權值和。

這個問題具有良好的可合并性，只需記錄當前區間中開頭結尾選法對應的最大值即可。

現在涉及到修改，由于我們是在前綴和意義下考慮所以修改是一段后綴，直覺上區間修改很難維護，可能只能分塊+重構什么的，但還是應該多試試的，有些性質得在編做法的過程中才能發現。

考慮線段樹維護上述答案，對于修改 $(t,x,v)$：

• 如果是修改螞蟻 $S$，等價于 $[x,\inf ]$ 區間中所有 $P?v$，$Q+v$，顯然我們只需要在當前線段樹節點遞歸到 $x\le l$ 時快速更新答案即可，那么容易發現影響是 $P..P$ 會 $?v$，$Q...Q$ 會 $+v$，其他不變，可以直接打 tag。
• 如果修改方糖 $T$，就是讓 $[x+L,\inf ]$ 中 $P+v$，$[x?L,\inf ]$ 中 $Q?v$。還是考慮線段樹遞歸的過程，遞歸邊界有幾種：
  • $r<x?L$，沒影響，直接 return。
  • $x+L\le l$，和修改 $S$ 類似，直接打 tag 即可。
  • $x?L\le l,r<x+L$，這比較困難，因為這樣的區間的四種答案是受到所選 $Q$ 數量的影響的，無腦想法是維護凸包什么的。但我們有性質！注意到這樣的區間長度 $\le x+L?1?(x?L)=2L?1$，那么形如 $Q...P$ 一個點都不會選，$P...Q$ 最多選一組 $PQ$，$P...P$ 最多選成 $P$，$Q...Q$ 最多選成 $Q$，所有的 $Q$ 數量都是固定的，可以直接打 tag 。

真好。

?

hall 定理輔助構造 / 猜結論

五花八門，具體題目具體應用。

AT_agc037_d [AGC037D] Sorting a Grid

好玩，喜歡。

發現本質上要為每個元素分配一列，然后過程是 起點 $\to$ 這一列，起點行 $\to$ 這一列，終點行 $\to$ 終點

限制是不能有倆起點 或者 終點在同一行的元素分配到了同一列。

繼續把限制拆開看，先從每行選一個起點，要求起點對應終點所在行互不相同，這就很二分圖匹配了。

左部是起點行，右部是終點行，連邊就表示一種元素，每次選一組完美匹配出來分配到同一列上。

就是說我需要 $m$ 組邊不交的完美匹配，這還剛好是 $m$ 正則二分圖，對完啦！

再放個東西：邊染色

AT_agc029_f [AGC029F] Construction of a tree

神秘題，不喜歡。

首先感受到可以用類似 hall 的條件判無解。

樹上連邊很難刻畫；但考慮為每個點分配父親，也就是分配父親所在集合，這就是簡單的匹配問題了。

這樣最后節點會剩下一個，不妨認為它是根，然后從它開始 dfs 建樹，可以證明遍歷不了所有點的話就無解。

還有記住二分圖匹配可以跑 $10^5$！！

P9070 [CTS2023] 琪露諾的符卡交換

逆天。

想想什么是好做的：我可以使得每一列恰好是 $1～n$ 的排列！

然后呢？我可以交換 $(i,j)(j,i)$，把矩陣轉置！

我靠，做完了！

?

逆用 hall 定理

顧名思義，有時候列出了 hall 條件的式子，就可以轉化成限制二分圖有完備匹配，某些題里后者比前者可做。

CF1519F Chests and Keys

列出來 $Bob$ 收益 $>0$ 的式子發現就是 hall 條件，那么直接轉化成存在完備匹配。

數據范圍很小，無腦記狀態 $dp$ 就行。

?

不知道和 hall 有什么關系的題

反正他放到作業里了，我也不知道有啥關系。

CF103E Buying Sets

考慮怎么刻畫 子集個數等于子集并 這個條件，由于求最小而且它保證了那個條件，于是可以轉化成 $\inf \times (子集并?子集個數)$，貢獻拆開。

然后就是選一個子集就選它的所有元素的限制，這顯然是個最大(小)權閉合圖，網絡流即可。

記住 $Dinic$ 復雜度可以寫成 $n^{2}m$ ，與邊權無關的。

好像有神秘二分圖匹配做法，不理解。

LibreOJ β Round #3 緋色 IOI（懸念）

干脆你叫 <填數游戲2> 算了，噢原來你比填數游戲早啊

一模一樣的建圖，一模一樣的觀察，一模一樣的難寫。