Gale
稳定婚姻问题(Gale-Shapley算法)
前言 今天 duck、香饽饽老板和彬彬一起出了个模拟赛,赛时T2想到了跟正解很接近的做法,但最后还是打挂了then喜提0pts,后面 duck 讲题的时候才知道是稳定婚姻板题。 看完证明之后觉得很妙,遂开坑。 只是简单整理,图一乐子吧算是。 说是稳定婚姻问题,但其实我觉得更合适的叫法是属性稳定分配问 ......
Gale-Ryser 定理
给定两个非负整数数列 $p_1 \ge p_2 \ge \dots \ge p_n$ 以及 $q_1 \ge q_2 \ge \dots \ge q_m$ 满足 $\sum_{i = 1}^n p_i = \sum_{i = 1}^m q_i$,存在一个简单二分图使得左部点的度数分别为 $p_1, ......