一些疑问
查看原帖
一些疑问
224336
AFewSuns楼主2023/6/20 16:08

为什么每个点最多走 1000 次,等价于每个点最多走 1 次?

换句话说,将一张二分图复制 1000 次,不同层之间的 (u,v)(u,v) 也有连边,为什么这张大图的最大匹配等于原图的最大匹配*1000?

如果上面的结论是错的,那么让结论再弱一点,为什么询问一个点是否一定包含于大图的最大匹配中,等价于询问一个点是否一定包含于原图的最大匹配中?

看了很多题解都没有解释,可能自己理解错了,想请教一下各位大佬

2023/6/20 16:08
加载中...