最大权闭合子图 闭合子图 定义有向图的一个闭合子图是该有向图的一个点集，其中这个点集中的所有点的出边连向的还是点集中的点。 最大权闭合子图 给有向图的点加一个点权，能得到的点权最大的闭合子图。 网络流模型 将所有正点权的点的点权全部加入答案。接下来我们将原来正点权的点变成负点权。现在图上全是负点，我们需要尽量选最少点权使图符合条件。 设超级源点和超级汇点。 将超级源向所有...

算法介绍 最大流问题是指在一个有向图中，从一个源点到一个汇点，最大化流量，使得所有边的容量都大于等于 0。 dinic 算法是一种高效的求解最大流问题的算法，其时间复杂度为 \(O(EV^2)\)。 dinic 算法的基本思想是，通过增广路算法，找到一条从源点到汇点的增广路，然后通过深度优先搜索（DFS）算法，在增广路上进行流的增广，直到不能再增广为止。 步骤 初始化 fl...

路径覆盖 路径覆盖指一个路径的集合中所有路径点集的并集为原图点集。最小路径覆盖使路径集合大小最小。 路径覆盖分为可否重复选点两种。可重复选点在建模中加大流量即可。 网络流模型 建超级源 \(S\) 和超级汇 \(T\)，将每个点拆点。 将 \(S\) 向所有点 \(i\) 连边，将所有点 \(i'\) 向 \(T\) 连边。 对于原图边集，每一条边 \(u\) 向 ...