前几天考试有一个建出最大流模型，转为最小割，然后模拟最小割的套路。
这一个套路并不是少见的。在 Gale-Ryser 定理和 Erdős–Gallai 定理的证明都体现了这个想法。
Gale-Ryser 定理：我先阅读了博文的 ycx060617 的评论的对 Gale-Ryser 定理的证明，略去。
Erdős–Gallai 定理：非增序列 \(d_i\) 可能作为简单图的度数序列的充分必要条件是
\[\displaystyle \sum _{i=1}^{k}d_{i}\leq k(k-1)+\sum _{i=k+1}^{n}\min(d_{i},k),\forall k\\ 2\mid\sum d_i \]建出网络流图：\(S\) 向点 \(x_{1:n}\) 连边权值为 \(d_{1:n}\)，\(y_{1:n}\) 向 \(T\) 连边权值为 \(d_{1:n}\)，\(x_i,y_j\) 连权值为 \(1\) 的边当 \(i \neq j\)。
有解当且仅当最大流为 \(\sum d_i\)，且中间边的有流边是配对的。
标签：Erd,定理,Gallai,Gale,Ryser,7.1,sum From： https://www.cnblogs.com/british-union/p/18278906/71xianhua