Gale-Shapley 算法

挺简单的一个算法，用于解决稳定婚姻问题。

稳定婚姻问题：一些男人和一些女人，每个男人都有对女人的排名，每个女人亦有，求一组最优秀的匹配。

考虑维护一个落单男人的队列，初始全部落单。每次取出队头并按该男人的眼光枚举每一个女人进行配对，如果这个女人落单，或者这个女人目前对象劣于当前男人，就配对，并将新的落单男人入队，注意当前男人配了对后就 break。

例题：UOJ41 矩阵变换

题目可以看成行与数字的配对。

设 \(p_{i,j}\) 为第 \(i\) 行的数字 \(j\) 所在位置，那么一组解不合法，即存在两行 \(i,j\)，其分别配对的两个数字 \(x,y\)，有 \(p_{i,x}<p_{j,x}<p_{j,y}\)。这启迪我们：行要匹配位置尽量左的数字，数字匹配尽量让它 \(p\) 大的行，用 GS 算法即可。