daicon

题解

/ 注册

全部文章 / 题解（共2篇）

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

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

二分图图论网络流

2020-09-19

0 463

2020牛客暑期多校训练营（第一场）H. Minimum-cost Flow

题解由于所有边的容量相同，所以可以得到一个性质，的流量在图中形成了k条1-n的路径，每多u的流量多形成一条路径（可能会导致原路径改变，但是只会在到时发生改变），这u的流量所用的花费是相同的，所以考虑u和v的倍数关系，预处理出u为1，v从1到100的花费，然后询问时直接求出对应的花费代码 #inc...

图论网络流

2020-09-19

0 457