/*
3 最小点覆盖、最大独立集、最小路径点覆盖(最小路径重复点覆盖)
  最大匹配数 = 最小点覆盖 = 总点数 - 最大独立集 = 总点数 - 最小路径覆盖

匹配/匹配边: 与其他边没有公共节点的一条边, 我们称这条边为一个匹配/匹配边.
匹配点: 匹配边上的点
非匹配点: 不在匹配边上的点
非匹配边: 图中两点之间的边不是匹配边的边
最大匹配(匹配边数量的最大值): 最多连多少条边, 使得所有的边无公共点
⭐增广路(径): 一边的非匹配点到另一边的非匹配点的一条非匹配边和匹配边交替经过的路径. 
  通俗:由一个未匹配的顶点开始，经过若干个匹配顶点，最后到达对面集合的一个未匹配顶点的路径，即这条路径将两个不同集合的两个未匹配顶点通过一系列匹配顶点相连。
初始:匹配边为一根线(-),非匹配边为两根线(--)
1 o  -  o 2
     \/
     /\
3 o     o 4  

此时3->2->1->4就是一条 非匹配边上的点3->非匹配边上的点4的增广路径
通过该增广路径可以让3-2匹配,1-4匹配从而实现最大匹配

(只要有一条增广路径就能多一组匹配, 最大匹配 <=> 不存在增广路径)

最小点覆盖问题
定义: 给我们一个图, 从中选出最少的点, 使得图中的每一条边至少有一个顶点被选
三个匹配边 = 1(\),2(\),3(-) 
  o    o
     \1
  o    .  选出最少的点(标记为".") 使得每一条边的两个点中起码有一个被选
     /
    /
  o    o
     \2
  o    .
  . ——3o
    \
     \
      o
在二分图中
    最小点覆盖==最大匹配数
    证A = B
    则需证最小点覆盖A ≥ 最大匹配数B - 最大匹配m-最少要选m个点来覆盖m个边(匹配里两两没有交点)
          最大匹配数B = 最小点覆盖A等号可以成立 -  构造一种方案 --由于最小点覆盖是所有方案的最小值
构造:
1 求最大匹配(匈牙利)
2 从左边每个非匹配点{a,b}出发 向右边做一遍增广(两条横虚线- -)
  o    o
     \
 ao - -.  
     /
    /
  o    o
     \
 bo - -.
  . —— o
    \
     \
      o
3 标记所有经过的点 标记为。 而未被经过的点依然是o
  。   o
     \      -> e1
 a。- -。3 
     /
    /
  。   o
     \      -> e2
 b。- -。2
 1. —— o    -> e3
    \
     \
       oc
 左部所有未被标记的点{1}和右边所有被标记的点{2,3}
1 左边所有非匹配点一定都被标记了(它们是出发点) / 左边未被标记的点一定是匹配点(1)
2 右边所有非匹配点一定没被标记(否则就找到了增广路) / 右边所有被标记的点一定是匹配点(2,3)
    回顾增广路定义:从左边非匹配点->右边非匹配点的路径
                    而被标记代表从左边非匹配点出发走到了右边的非匹配点
3 对于匹配边 左右两个点要么同时被标记 要么同时不被标记(因为在寻找增广路的过程中，左部匹配点只能通过右部到达。)
⭐对每个匹配边必然只选一个点 - 选右边被标记的点{2,3}/选左边没被标记的点{1}
    此时:我们选的点(.)的数量==匹配数(e1、e2、e3)


0 首先定义当前满足假设:左边右边都在匹配边肯定是被最大匹配树中得匹配边覆盖的
不在匹配中的点所在的边是否被最大匹配数中的匹配边覆盖？
1 左边非匹配点i → 右边匹配点j (如边a-3,边b-2)
    因为i是出发点，所以j一定被标记。而我们选了右部所有被标记的点(⭐处)，因此这样的边也被覆盖。
2 左边匹配点i    → 右边非匹配点j(如边1-c 右边非匹配点==未被标记的点)
    i一定没有被标记，否则再走到j就找到了增广路。而我们选了左部所有未被标记的点(⭐处)，因此这样的边也被覆盖。
    画出i被标记的例子就可说明为什么
 0。-- 。 ->被标记的点都是能从左边非匹配点0出发经过i后才标记i的
     /       如果能从i->j,则说明找到一条0-j的增广路,则可以多出一条匹配边 
    /        与最大匹配矛盾
 i。—— o 
    \
     \
       o j
3 左边右边都不匹配(此时可以在最大匹配加一条新的边) -- 这和当前这个匹配是最大匹配矛盾

因此 我们构造出的情况恰好选3个点且将最大3条匹配边覆盖住
*/

原作者:仅存老实人