最小路径覆盖

· · 个人记录

最小路径覆盖就是选出最少数量的互不重合的路径，使其包含所有的点。也即，每个点在且仅在一条路径上头。

题解区队爷提到：对于这种“对于每个，有且只有”的性质，可以抽象成二分图。

每个点与两个点连接，分别是作为入点和出点的情况。那么我们考虑把每个点抽象成两个点 (u, u + n)，然后向 u 的每个出点连边 (u + n, v)。这样，我们就能求出来合并的数量，以 n 减去就是路径数量。