自动搬运

查看原文

来自洛谷，原作者为

	Ajwallet 厌倦追寻，一觅即中

搬运于2025-08-24 21:41:19，当前版本为作者最后更新于2018-06-24 13:11:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

更改内容：图片稍有改动

这里给大家提供一下题目大意和建模思想

题目大意

有$k$种类型和$n$个题目，每个题目会适应部分类型，一种类型可能需要多种题，一道题可能多种类型都需要，但一道题只能满足一种类型，现要求出满足出完所有类型的题目的方案

解题思路

网络流擅长于解决各种有要求的匹配，显然这道题是有条件的匹配，可以用最大流来解决。

首先建立超源点和超汇点，源点与试题相连，汇点与类型相连，对应试题与对应类型相连

现在我们来考虑边的容量

因为一道题只可以有一个，所以源点和试题的边的容量为1

同理一道题只能满足一种类型，所以试题和类型的边的容量也为1

而需要满足的类型是有多个的，所以类型与汇点的边的容量为所需类型的数量

如图

这时跑最大流即可

统计方案只需找到没有被割掉的边（可能有人不懂什么是被割掉，因为最大流=最小割）。然后输出其即可，需要注意的是，输出的不能是汇点