1 solutions
-
0
结论:最终一定能取到最大匹配。
可以通过递归完成构造。
Key Obeservation:总存在一个最大匹配,使得存在一个学生选到了其最喜欢的小班课。
证明:令 为一组最大匹配。 分别为 最喜欢的小班课。
若存在 不为任何一个 ,那么直接将 调整为 即可。
否则 均连边后构成的二分图,其恰好有 个结点和 条边。而左部每个点度数为 ,可以重复找到右部度数为 的点 ,删去 和 ,因此会被删掉 个点和 条边,可以递归下去。最终一定所有点度数都为 ,构成若干个环。对于每个环上所有点将 均调整为 即可。
于是我们有如下做法:每次任意找到一个选到其最喜欢的小班课的学生,将其放入队列的第一个,将该学生删除,课容量减一,如果课容量为 删去该课程。然后递归构造。
实际实现中,首先需要一个二分图匹配,这里的复杂度是 。上述的证明可以直接实现成构造,单次构造是 的,复杂度为 。具体实现还可以用一个小技巧,即仅保留 这些边之后随机顺序做二分图匹配,这样每个环有 的顺序改变顺序,每一次匹配是 的,期望复杂度同样也是 的。
- 1
Information
- ID
- 37
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- (None)
- Tags
- (None)
- # Submissions
- 0
- Accepted
- 0
- Uploaded By