集训队作业kings quest解题报告

1、Kings Quest解题浙江问题描述从前有一个国王，他有 N 个儿子。皇宫里还有 N 个美丽的，并且国王知道每一个王子喜欢的常的。们。王子们都年轻强壮并且富有智慧，所以一个王子喜欢很多也是很正国王找到巫师，告诉巫师每个王子所喜欢的们，并且要求巫师找到案，每一个王子都娶到一个自己喜欢的。当然，一个只能一个王子。巫师提交了案，国王看了后说：“我挺喜欢你的方案，但我不是十分满意。我还想知道每一个王子能娶的所有，当然，他娶了某个之后剩下的其它王子还是可以找到自己喜欢的人作为自己的伴侣。”国王给的这个问题对于巫师来说太难了，你必须帮助巫师解决这个问题从而保住他的脑袋。输入第一行包含一个整数 N（N20

2、00)，表示王子的个数。接下来行 N 每行给出一个王子喜欢的列表。最后一行包含 N 个整数，描述了巫师提交的列表每个王子的结婚对象。列表保证合法。输出输出 N 行，对于每一个王子，先输出 Li，表示他可以娶的个数，接下来 Li 个数表示他可以娶的Sle Input42 1 22 1 22 2 32 3 41 2 3 4（递增顺序输出）。Sle Output2 1 22 1 21 31 4算法分析题目给了一个二分图以及一个初始的完备匹配，求出 X（王子集合）中每个点能匹配的点，保证剩下的点依然存在完备匹配。设 Wifei为巫师列表中王子 i 的准新娘，Husbandi为巫师列表中一个很直观的想法

3、就是，对于每一个王子 x，枚举他喜欢的每一个i 的准新郎。y，检查剩下 N-1个王子和 N-1 个是否还存在完备匹配。因为题目已经给出一个初始完备匹配，所以我们不需要重新做匹配，而只需要找一条从 Husbandy到 Wifex的增广路（如下图）（黑色箭头为原有匹配，红色箭头为检查的边，蓝色虚线箭头为需要寻找的增广路)（深桔色点为 x，浅桔色点为 y，深蓝色点为 Hasbandy，浅蓝色点为 Wifex）找一次增广路的复杂度为O(n + m) , 枚举边O(m) , 所以总时间复杂度为 O(m*(n+ m)。当给定的是一个完全二分图的时候，复杂度约为 O(n5)。对于 N=2000,无法接受。需

4、要发掘问题的性质，从而找到更好的方法。对于王子 x, 如果y (y Wifex)可以成为他的新娘，那么 y 与 Wifex之间有什么关系呢？由刚才的想法，如果y 可以成为王子 x 的新娘，那么从 Husbandy出发可以找到一条到达 Wifex的增广路。加上原来存在的两条匹配，变成了什么呢？原有匹配，新增匹配，增广路，三者再一起了一个圈！进一步观察这个圈，可以发现，它是由匹配边（初始匹配中的边），非匹配边交错组成（二分图中圈的长度必为偶数）的一个“交错圈”。定理 那么如果i 和 Wifex同在某一个交错圈中，并且王子 x 也喜欢 i ，那么 i也是可以王子 x 的。证明：显然的，x - Wif

5、ex 这条匹配边必然在交错圈中（因为 Wifex只有一个匹配点x，而交错圈中每个点都连出去一条匹配边和一条非匹配边）。从交错圈中 Wifex的非匹配边出发到达 i 的这一段中（结束于一条匹配边），将所有的匹配边与非匹配边对调，经过这个操作，只剩下 x 和i 是没有被匹配的。而 x 喜欢i,所以增加新的匹配边 x-i ，依然是一个完备匹配。所以 i 可以王子 x.。于是问题就转化为询问 Girl 们是否在一个交错圈中。构建一个新图 G0 , 对于每一个王子 i , 从 Wifei向每一个 i 喜欢的连一条有向边。对 G0 求强连通分量。在同一个强连同分量中的两个点必存在于某个交错圈中（G0 中的每条边都是原图中的一对交错边）。如果j 跟 Wifei在同一个强连通分量中并且王子 i 喜欢 j，那么 j 也是符合条件的新娘候选人：）。这样一来，问题就解决了。只需要求一次强连通分量。时间复杂度为 O(n + m)。附录King_force King.cpp来