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

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


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

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


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

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


匈牙利模板:

int find(int x)
{
	for(int i=1;i<=p;i++)
	{
		if(g[x][i]&&!vis[i])
		{
			vis[i]=1;
			if(!mat[i]||find(mat[i]))
			{
				mat[i]=x;	return 1;
			}
		}
	}
	return 0;
}
void hungary()
{
	for(int i=1;i<=p;i++)
	{
		memset(vis,0,sizeof vis);
		if(find(i))	res++;
	}
}