daicon

分类

题解(9)

/ 注册

全部文章（共1篇）

2020牛客暑期多校训练营（第一场）I. 1 or 2

题解我们考虑匹配问题，每条边会关联两个点，那么肯定是点和边有关联；每个点需要减的度数是，因此每个点拆成个点，然后每条边拆成两个点和，连完边之后这就是一个二分图，跑完图匹配之后必定还有某些边没有匹配上（因为每一个拆出来的点都会连条边，最大的情况也不过是全部都匹配上）；但是我们对于边拆出来的点也有限制...

二分图图论网络流

2020-09-19

0 463