匈牙利算法可以解决的图的问题：（二分图）
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;
}
