4.4 KiB
最小路径覆盖 与 最大独立点集
一、基本概念
最小路径覆盖是在DAG有向无环图中进行讨论的：
花了好长时间，用于找了几篇能看懂的最小路径覆盖。
定义：通俗点讲，就是在一个有向图中，找出最少的路径，使得这些路径经过了所有的点。
最小路径覆盖分为 最小不相交路径覆盖 和 最小可相交路径覆盖。
-
最小不相交路径覆盖 每一条路径经过的顶点各不相同。如图，其最小路径覆盖数为
3。即1->3>4，2，5。 -
最小可相交路径覆盖 每一条路径经过的顶点可以相同。如果其最小路径覆盖数为
2。即1->3->4，2->3->5。
特别的，每个点自己也可以称为是路径覆盖，只不过路径的长度是0。
二、最小不相交路径覆盖
算法：把原图的每个点V拆成V_x和V_y两个点，如果有一条有向边A->B，那么就加边A_x−>B_y。这样就得到了一个二分图。那么 最小路径覆盖 = 原图的结点数 - 新图的最大匹配数。
证明：一开始每个点都是独立的为一条路径，总共有n条不相交路径。我们每次在二分图里找一条匹配边就相当于把两条路径合成了一条路径，也就相当于路径数减少了1。所以找到了几条匹配边，路径数就减少了多少。所以有
最小路径覆盖 = 原图的结点数 - 新图的最大匹配数。
因为路径之间不能有公共点，所以加的边之间也不能有公共点，这就是匹配的定义。
说的拆点这么高深，其实操作起来超级超级简单，甚至没有操作。
简单的来说，每个顶点都能当成二分图中作为起点的顶点。
三、最小可相交路径覆盖
算法：先用floyd求出原图的传递闭包，即如果a到b有路径，那么就加边a->b。然后就转化成了最小不相交路径覆盖问题。
证明：为了连通两个点，某条路径可能经过其它路径的中间点。比如1->3->4，2->4->5。但是如果两个点a和b是连通的，只不过中间需要经过其它的点，那么可以在这两个点之间加边，那么a就可以直达b，不必经过中点的，那么就 转化成最小不相交路径覆盖。
题单
POJ 3041 Asteroids
【最小点覆盖=最大匹配数】
HDU \ 1151—Air Raid
【最小可相交路径覆盖，Floyd传递闭包, 转为 最小不相交路径覆盖】
POJ 1548 Robots
【二维排序、类似于传送闭包建图、转为 最小不相交路径覆盖、匈牙利算法；或者LIS+Dilworth】
AcWing 2549. 估计人数
【可相交的最小路径覆盖 问题转化成 不相交的最小路径覆盖 问题，最小路径数=图中节点总数-节点最大匹配度】
POJ 2594 Treasure Exploration
【可相交的最小路径覆盖 问题转化成 不相交的最小路径覆盖 问题，最小路径数=图中节点总数-节点最大匹配度】
POJ 3692 Kindergarten
【最大独立点集=点数-最大匹配数，反向建图,靠的是分析，不是靠背定义】
POJ 1466 Girls and Boys
【最大独立点集=点数-最大匹配数，没给出男女，只能复制点，然后匹配数除以2】
POJ 3216 Repairing Company
【Floyd求多源最短路，通过u开始时间+持续时间+走路时间<=v开始时间，找到可达节点,然后就是最小路径覆盖问题】
POJ 3020 Antenna Placement
【两个城市间建边描述一个无向网，无向图，所以匹配数除以2】
LightOJ 1152 Hiding Gold
【全新建图、离散化、节点数减去最大匹配】