最小权点覆盖集的相关概念

点覆盖集： 给定一个有无向图 $G(V, E)$，选择图中的某一个点集，使得每一条边都至少有一个端点在被选的点集中，则将这样的点集称为原图的 点覆盖集

最小权点覆盖集： 给定一个有向图 $G(V, E)$，每个点上有一个非负的权值，选出的权值和最小的点覆盖集被称为 最小权点覆盖集

如何求最小权点覆盖集

最小权点覆盖集问题在一般的图中是一个 NP 完全问题（NPC 问题），目前证明出来只能用爆搜来做，时间复杂度一定是指数级别。

但是在二分图中存在一种非常高效的做法。

首先对于二分图中，如果所有点的权值都是 $1$，那么久可以用匈牙利算法直接求，且最大匹配数 $=$ 最小点覆盖数 $=$ $n-$ 最大独立集数。

如果所有点的权值不一定是 $1$，那么就不能用匈牙利算法来求，只能用网络流去解决这类问题。

那么我们如何用网络流来解决一个点权任意且非负的最小权点覆盖集的问题呢？

对于一个二分图，应该有两排节点，另有一个源点一个汇点，两排节点之间存在若干条边，每条边都至少要覆盖一个点，因此可以将这些边的容量设置为 $+\infty$，保证割边不出现在中间。对于每条边来说，这两个点至少要有一个被选，类比到流网络中相当于是这两个点和源点、汇点之间的边要是割边，而最小权点覆盖集和最小割都是求最小值，因此我们就可以往这个方面去考虑。

接下来需要具体证明能否用最小割模型解决二分图的最小权点覆盖集问题，每个点都有点权，左排节点的权值可以放到从源点到这些点的边上，而右排节点的权值可以放到从这些点到汇点的边上。由于点权是非负的，所以容量是合法的。中间所有边的容量同以上思路设置为 $+\infty$。

然后我们可以看一下所建的流网络和原问题的点覆盖的集合之间是否存在关系，首先定义一个概念，将所有只包含和源点、汇点相连的边作为割边的割称为简单割（仅限于本题）。显然，简单割是所有割的一个子集。

可以发现，最小割一定是一个简单割，因为最小割就是最大流，而从源点出发的所有边都是有限容量，所以最大流是有限值，最大流等同于最小割也是有限值，因此最小割一定不包含中间那些容量是 $+\infty$ 的边，所以最小割一定是简单割

对于流网络中任意一个简单割 $[S, T]$，如果割边是和源点相连，则将对应的左排节点加入点覆盖集，如果割边是和汇点相连，则将对应的右排节点加入点覆盖集。这样选出来的点集一定是原图的一个点覆盖集，即保证每条边至少选中一个点。如何证明呢，如果某一条边的两个点都不在点覆盖集中，那么说明两个点和源点、汇点之间的边都不是割边，这样就能通过这一条路径从源点搜到汇点，这就不是一个简单割了，由此反证得出每条边的两个点至少有一个点被选中。这样我们就能将任意一个简单割对应到任意一个点覆盖集。

对于任意一个点覆盖集，和上面通过简单割构造点集的方法相反。这里枚举点覆盖集中的所有点，如果该点是左排节点，则从源点到该点的边设为割边，如果该点是右派节点，则从该点到汇点的边设为割边。然后从源点往下搜索，搜到的所有点放到 $S$ 集合中，搜不到的所有点放到 $T$ 集合中。如此得到一个简单割，首先所有割边必然在左、右两侧，所以如果是割就一定是简单割，那么是不是一个合法的割呢，只需要看能都从源点走到汇点即可，这里假设从源点能走到汇点，那么就必然经过了中间某一条边，说明这条边的两个点都没有在点覆盖集中，这就不是一个合法的点覆盖集，就矛盾了，由此反证得出从源点一定走不到汇点，所以构造出的是合法的简单割。

综上所述，证明了任意一个简单割的集合和任意一个原问题的点覆盖集是一一对应的，然后需要看一下它们之间的数量关系，可以发现任意一个简单割的容量就是它所有割边的容量之和，由于已经设置这些边的容量就是对应点的权值，所以选出的割边的容量之和就等价于原图中选出的三个点的权值之和，就是对应的点覆盖集的权值之和。所以两者的关系是相等的关系。

到此为止，总结了求最小权点覆盖集的整个思路，按照指定的建图方式求一遍最小割就是最小权点覆盖集的权值之和。