题目来源 P3386
解答
二分图(通俗解释):
一个图,它可以分成两部分,使得每个部分内部没有边相连,而这两部分相互有边相连,此图称为二分图。
这就是一个标准的二分图,两个用黄色框框起来的部分中的点相互没有连线。
引子
想一下坐板凳的问题:
有 $n$ 个人,$m$ 个板凳,每个人只能坐给定的某些板凳,那么,怎么让最多的人坐在板凳上呢?
显然的是,一个板凳上只能有 $1$ 个人。
那么,不妨把人看成一个集合(点集),板凳看成另一个集合,这两个集合内部是显然不会相连的(比如人不能坐在人上,板凳不能坐在板凳上)。
因此很容易就会想到用二分图来做。
对应关系:某个人坐某个座位。
以下是没有优化的伪代码:
1 | bool sit(a):// 让a号人来抢位置 |
时间复杂度优化
每次调用 sit()
函数的时候,$a$ 都会从头到尾判断哪个座位能坐,哪个又不能坐,有重复。
想到用一个 $bool$ 二维数组 used
来存储 $a$ 是否找过这个点,$true$ 为找过,$false$ 为没找过。
空间复杂度优化
注意到每次都会尝试给不一样的 $a$ 安座位,而每次都只针对 $a$ 这一个人来操作,所以数组可以由二维降到一维,每次在 main
中调用 sit()
的时候清空即可。
因此我们得出以下优化的代码:
1 | bool sit(a): |
调用入口:
1 | for i=1 to n |
这样 $ans$ 就是我们要的最大匹配数,如果要求匹配方法,每次记录 used
就好了。
代码
1 |
|
本文作者:Xecades
本文链接:https://blog.xecades.xyz/drafts/solution-p3386.html
文章默认使用 CC BY-NC-SA 4.0 协议进行许可,使用时请注意遵守协议。
评论