2020牛客暑期多校训练营(第一场)

作者: ffacs 分类: Nowcoder 发布时间: 2020-07-15 14:27

H

题意

多组数据,每组数据给出一个费用流和多个查询,查询为在每条边的容量都为 $\frac{u}{v}$ 的时候,从原点输送 $1$ 个单位的流量到汇点所需的最小费用。

解法

注意到每条边的容量都相同,而 $\text{MCMF}$ 算法是每次找一条费用和最小的路径,然后加上最大的可行流。若容量相同则每次增广都等于直接删去这些边。所以增广的次序是不会变的。我们只需预先跑一次 $\text{MCMF}$ 将增广路径按顺序全部求出,然后就可以 $O(1)$ 处理询问了。

I

题意

一个无自环的无向图。问是否存在子图使得第 $i$ 个点的度为 $1\le d_i \le 2$ 。

解法

如果 $d_i\equiv 1$ 那么就是一个一般图匹配了。问题在于两个度为 $2$ 的节点之间如何建图。可以将一条边拆成两个点。度为 $d$ 的点拆成 $d$ 个点。如果这个图是完美匹配的则原图也存在完美匹配。否则不存在。在我们建的这个图中,边拆出来的点要么各自匹配两边的点,要么与自己匹配。

发表评论

电子邮件地址不会被公开。 必填项已用*标注