由已知婚姻匹配求出所有可出轨匹配。
因为稳定婚姻问题中的匹配都是完美匹配，因此也可以换一种说法，已知一个完美匹配，求出所有完美匹配。
这道题或许可能是我这辈子做的最后一道稳定婚姻问题……因为本来出的就少，感觉都是套路……
求稳定婚姻就是模拟的板子，判定和所有出轨匹配就是tarjan缩点……
尽管如此，但还是不得不学啊……
题意：
一个国王有很多个儿子，这些儿子有很多个喜欢的女孩。国王把这些女孩都找了过来，刚好儿子和女孩的数量相同。所以只能一夫一妻了。
国王要大臣给个可行方案，大臣给了。国王又要所有可行方案。大臣就烧脑子了。
儿子最多2000个……囧……厉害厉害
思路：
其实方法的话……基本还是和稳定婚姻的判定是一样的。稳定婚姻判定点这里
在求出所有强联通分量之后，找出男性的所有可婚配配偶 和 与他在同一个强联通分量的女性的交集。
从小到大输出这个交集就是我们要求的答案。
AC Code ( 时间略长……
#include
稳定婚姻的判定问题。 老实说，写了几题后发现稳定婚姻问题几乎都是板子题……囧…… 而且我作为入门题写的那道题好歹还披了一件外套，有几道完完全全的裸题写得我是非常的空虚…… 回到这道题，这道题应该算是稳定婚姻判定的裸题了。 假如我们再次无脑套模板，复杂度还是在( O(n^2) )左右。 我们从另一个角度来考虑。如果我可以找到一个相互出轨的夫妻，那就是不稳定的。 从而，对于一个已知的婚姻匹配，如果存在一对夫妻离婚，但不会对其他夫妻造成任何影响，那么这组婚姻匹配就是稳定的。 稳定婚姻的判定就是通过这种方式找到可以相互出轨的夫妻。 一个可行解法就是求强联通分量。对于已知匹配建立好单向二分图，对于可出轨匹配用反向边表示。然后求一下强联通分量。如果存在一组匹配，他们被染色的数量超过 ( 1 ) 是什么颜色呢？？ 那这个婚姻匹配就是不稳定的。 复杂度为Tarjan的复杂度，估计在( O( n ) ) 左右。 题意： 先给你一组婚姻匹配，再给你几组可出轨匹配，问你对于每一对夫妻，他们的匹配是否安全。 思路： 裸题啦，裸题，看了我上面的陈述就知道该怎么写了。 A…
第一次看了理论之后自己敲代码直接 1A ！！！蛤蛤蛤蛤！！！ 嗝～～ 稳定婚姻问题的定义与求解方法详见百度百科 中文维基上写的比较简单。 简单说一下个人理解与解法。个人感觉还是挺有趣的。 稳定婚姻问题是构建在男女双方的二分图基础上的。如果对于现有的一个男女匹配，存在一个男人 a 比起现在的妻子女人 a 更喜欢 女人 b 。而与此同时，女人 b 比起现在的丈夫男人 b ，更喜欢男人 a 。那么男人 a 与 女人 b 很可能会出轨。我们称这个婚姻匹配是不稳定的。 反之，如果不存在这个会出轨的男女匹配，则称这个婚姻匹配是稳定的。 稳定婚姻问题的求法在上面的中文维基上有伪代码，我也基本上按照这个理论敲的。 略为详细的步骤如下： 1. 为每一个男性与女性确定一个各自的异性在自己眼里的排名。但是记录方式不太一样，根据我的写法，男性需要记录的是排名第几是那个女性，女性需要记录的是这个男性排第几。 2. 将每个男性加入队列。尝试为每个男性按排名配偶，如果这个女性暂时没有配偶，那么暂时进行匹配。否则，与她现在的配偶进行比较。…
01分数规划之最优比例生成树……
这道题，好坑……
一开始WA了，然后找了一个博客，WA，照着敲，WA，再照着敲，WA，索性复制再改，WA，最后复制粘贴，他的也WA了。md
感觉我写题的时候很容易石乐志，然后就很难过题……
好几场比赛都验证了……
题意：
给你一张图上的所有点，由所有点得出每条边的两个权值，欧式距离与高度差。
要你和找出一个生成树，使得 高度差的和比上欧式距离和最小。
思路：
最优比例生成树的经典题。其实只要掌握了01分数规划的思想，你就照着prime敲就好了。
我这里用了迭代法，感觉迭代法更套路一些……而且速度比较快。
#include
分数划分之最优比例环。 分数划分中比较常见的限制之一，在图中筛选的必须是一个环。 本来在入门题的时候对于以下转换公式有考虑过这样的一个问题： $ \sum \left( \left( a_{i}-L\times b_{i}\right) \times x_{i}\right) $ 为什么只需要考虑 ( \left( a_{i}-L\times b_{i}\right) ) 与 ( 0 ) 之间的关系，而不用去管( x_i )了呢？明明取舍( x_i )也是对答案会造成影响的。 而实际上，举个例子，对于最优比例环来说，成不成环就是一个主要的筛选的过程。然后再是对于二分的值( L )，如果对于当前( L) 仍有可提升空间。若仍有提升空间，就说明( L)…
很早就想学的东西了……但是要学的实在是太多了…… 01分数规划是分数规划中最简单的，所谓01，就是对于每一件物品，他都是不同的，你只有取或者不取两种选择，没有在数量上太多的选择。就像01背包一样。 01分数规划 虽然考察的不多，套路也比较死，但是多校的时候着实出现过。记得应该是cls的那一场，记得是01分数规划的新操作…… 01分数规划是用来解决取舍导致的比例最值问题。解决该问题的方法有两种。 一种是二分，另一种是迭代，迭代法也称 Dinkelbach 算法。 二分法基于验证，迭代法基于直接计算，一般来说迭代法会更快一些。 两者写起来都非常简单。 入门资料推荐。具体思路不再细说。 入门题在这里。 入门资料中谈到，如果对于题目改成最小化，那么就尽量少选，不是很理解他的说法。 就我看来，把分子分母倒一下就转换过来了。 题意： 最裸的01分数规划，要你从 n 个中挑出 k 个使得比例最大。 就图片来说就是要你求这样的结果，当然是选取 k 个。 思路： 验证板子的题，因为它的限制只有一个，没什么好说的。…
CCPC网络赛的KMP模板题……
比赛期间因为被1003卡住了，这道题根本没时间去想……
本来一眼看去我也是想到AC自动机，只要吧字符串反转一下，就可以套用上一次的AC自动机直接求解。
但是模式串和匹配串都只有一个，建立AC自动机虽然可解，但有不必要的消耗。
这道题几乎卡掉了除了KMP以外的所有求这道题的其他解法。
题意：
给你两个串a , b，要你找出 b 串的所有后缀同时也是 a 串的子串。
然后按题意计算。
思路：
其实还是和上一道AC自动机有些类似之处。
但还是有很大不同，AC自动机可以在匹配的时候不断 fail 到前缀。
而KMP只能通过记录匹配，然后从后往前不断 next 累加。
AC Code
#include
南大所谓的最小费用有向图………… 什么 jb 玩意？？？？不是都叫最小树形图么……………… 这道题适合Yasola一起讨论的，虽然说一起讨论，但是对权值进行修改这一关键操作还是他想得 太巨了呀！！！ 然而最后还是差一点。 题意： 给你一张有向图，要你求最大树形图，同时满足最后一个结点的父亲字典序最小。 思路： 这个朱刘算法……有毒…… 朱刘算法真的是把原图毁的不成样子…… 然后我们两个就在这里踩了很多坑…… 首先认清一点，朱刘算法是可以求负权的。这就保证了最大树形图可解。 再是单独一个结点的字典序最小。 首先一个重要的操作就是对边权扩大处理。对于指向最后一个结点的边权我们让它与父亲结点编号联系起来。 联系方法： $ edges[i].cost = v == n ? -w * 1000 – 1000 + u : -w * 1000 $ 说一下我们的很多错误思路，不想看可以直接跳过。 1. 直接用pre 数组输出。 不可行，因为结点都已经缩点染色过了，边数组的起点终点不是原起点，原终点， 2. 开一个ori 数组记录每一个染色后的点的原起…