链接：

 

/* ************************************************************************** //二分图匹配（匈牙利算法的DFS实现）//初始化：G[][]两边顶点的划分情况//建立G[i][j]表示i->j的有向边就可以了，是左边向右边的匹配//G没有边相连则初始化为0//uN是匹配左边的顶点数，vN是匹配右边的顶点数//调用：res=hungary();输出最大匹配数//优点：适用于稠密图，Find找增广路，实现简洁易于理解//时间复杂度:O(VE) //顶点编号从0开始的 //************************************************************************** */

 

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define N 205#define INF 0x3f3f3f3fint n, m, un, vn, G[N][N], used[N], p[N];int Find(int u){    for(int i=0; i
        
       
      
     

 

 

最小顶点覆盖：在二分图中寻找一个尽量小的点集，使图中每一条边至少有一个点在该点集中。

　　最小顶点覆盖 == 最大匹配。

　　反证法证明：假设当前存在一条两个端点都不在最小顶点覆盖点集中，那么这么光芒四射的边定可以增大最大匹配边集，与最大匹配矛盾，所以得证。

 

最小路径覆盖：在二分图中寻找一个尽量小的边集，使图中每一个点都是该边集中某条边的端点。

　　最小路径覆盖 == 顶点数 - 最大匹配。

　　证明：因为一条边最多可以包含两个顶点，所以我们选边的时候让这样的边尽量多，也就是说最大匹配的边集数目咯。剩下的点就只能一个边连上一个点到集合里啦。

 

最大独立集：在N个点中选出来一个最大点集，使这个点集中的任意两点之间都没有边。

　　最大独立集 == 顶点数 - 最大匹配。

　　证明：因为去掉最大匹配两端的顶点去掉以后，剩下的点肯定是独立集。我们再从每个匹配里面挑选出来一个点加入到独立集中，也是不会破坏原有独立集的独立性的。