最大流(匈牙利算法)以及应用

匈牙利算法可以解决的图的问题：（二分图）
1.图的最小点覆盖数 = 图的最大匹配数；
2.图的最大点独立集 = 图顶点数 - 图的最大匹配数；
3.图的最小路径覆盖数 = 原图的顶点数 - 原图拆点后形成的二部图的最大匹配数；

二分图的定义：把顶点分成X和Y两个集合，每一条边的两个端点都分别在这两个集合里。

二分图的基本问题就是最大匹配了：在二分图中找一个边集，使得该边集所包含的边数最多。

基本算法是匈牙利算法，用DFS找增广路径，在此不多说了，详见：（写得十分透彻）

二分图之所以灵活，是因为有很多看似无关的问题都能转化到最大匹配的问题上来。

问题一：最小覆盖，寻找一个点集，使得图中每一条边至少有一个点在该点集中，且该点集所包含的点数最少。（最小覆盖的情况下，每边条有且仅有一个端点在该点集中）。

定理：二分图最小覆盖等于二分图的最大匹配。

证明：设最大匹配数为m。

1：至少要m个点

证：因为二分图的最大匹配数为m，而每条边的端点互不相同，故至少要有m个点，才可以覆盖到所有的边。

2：最多要m个点

证：若存在m+1个点，则必有一条边的两个端点在该点集中，删去其中一点仍可以保持每条边被覆盖到，以此类推，大于m个点的点集都不是最小覆盖。

综上：最小覆盖的点集所包含的点数等于m，即二分图的最小覆盖等于二分图的最大匹配。

经典问题：PKU3041 Asteroids，给定一个矩阵，矩阵上有若干个障碍物，你可以一次清除一行或者一列的障碍物，问最少的清除操作需要几步。

建图时，以障碍物为边，行为X集合，列为Y集合建立二分图，若在map[i][j]上有一个障碍物，则将第i行与第j列之间连上一条边。问题就转化成了最小覆盖问题，最小覆盖=最大匹配。

该题的变型是PKU2260 Muddy Fields，一张图上有若干的泥点，现在要用单位宽度的木板（长度不限）盖住这些泥点，且不能盖住干净的点。同样是以泥点为边，但这个时候不是单纯的一 行或者一列为一个集合了，而是以行上的连通块为X集合，列上的连通块为Y集合，如果连通块i和j相交，则将i与j之间连一条边。同样是最小覆盖=最大匹 配。

推荐题：PKU1325

问题二：最小路径覆盖，用最少的不相交简单路径覆盖所有的有向无环图上所有的顶点

定理：最小路径覆盖数=结点数-最大匹配数

证明：对于每条路径上的顶点，除了最后一个以外都有它的后继，则所需要的路径数就是没有后继的结点个数，对于n个结 点，我们把集合X和Y分别放入这n个结点，若i的后继是j，则i与j之间连一条边，又因为路径之间不相交，则每个结点都有惟一的后继，要使没有后继的结点 个数最少，则要求有后继的结点个数最多，即满足最大匹配。故最小路径覆盖数=结点数-最大匹配数。

经典问题：PKU1422 Air Raid，一张图上若干个点之间有单向边，且不存在环，现在你可以任意安排伞兵降落到几个点上，然后让他们遍历所有的点，要求不能有两个或以上的伞兵访问同一个点。

题目和最小路径覆盖的描述完全一样。最小路径覆盖数=结点数-最大匹配数。

该题的变型是PKU2594 Treasure Exploration，题目很相似，唯一不同的是没有了最后一句的限制，即一个点可以被多个人访问。

我一开始以为没了这个限制就要用别的方法来做了，但用搜索又想不好怎么标记，后来看了discuss，惊奇地发现 tq师兄和gsy师姐的留言，锁定到一个关键词：传递闭包。然后就做了一次floyd，再按照最小路径覆盖便过了，对于这个算法我的理解是：当某些相交的 点被匹配了以后，由于做过了传递闭包，其他的路径上的点就可以跳过相交点而直接与下一点匹配，这样就符合了题意。

问题三：最大独立集，找一个点集，其中任意两点在图中无边，且该点集包含的点的个数最多

定理：二分图最大独立集=结点数-最优匹配（一般图的最大独立集是NP完全问题）

证明：易知最大独立集的补集必定覆盖了所有的边，为使最大独立集包含的点的个数最多，我们要求的补集就成了最小覆盖，二分图的最小覆盖=最大匹配。故二分图的最大独立集=结点数-最大匹配。

经典问题：PKU1466 girls and boys，给出每个人与哪些异性有关系，求一个最大集合，其中的人都没有关系。

建图时把一个人拆成两个，分别放在X和Y集合里，这样求出的最大匹配/2就是实际的最大匹配数，避免了区分男的和女的后再放到两个集合里去。

c语言实现的匈牙利算法，思路很清晰！
#include 
#include 
#define MAX 102
 
long n,n1,match;
long adjl[MAX][MAX];
long mat[MAX];
bool used[MAX];
 
FILE *fi,*fo;
 
void readfile()
{
	fi=fopen("flyer.in","r");
	fo=fopen("flyer.out","w");
	fscanf(fi,"%ld%ld",&n,&n1);
	long a,b;
	while (fscanf(fi,"%ld%ld",&a,&b)!=EOF)
		adjl[a][ ++adjl[a][0] ]=b;
	match=0;
}
 
bool crosspath(long k)
{
	for (long i=1;i<=adjl[k][0];i++)
	{
		long j=adjl[k][i];
		if (!used[j])
		{
			used[j]=true;
			if (mat[j]==0 || crosspath(mat[j]))
			{
				mat[j]=k;
				return true;
			}
		}
	}
	return false;
}
 
void hungary()
{
	for (long i=1;i<=n1;i++)
	{
		if (crosspath(i))
			match++;
		memset(used,0,sizeof(used));
	}
}
 
void print()
{
	fprintf(fo,"%ld",match);
	fclose(fi);
	fclose(fo);
}
 
int main()
{
	readfile();
	hungary();
	print();
	return 0;
}