暂时只包括与最大匹配相关的问题。
求最大独立集，最小路径覆盖等等大多数题目都可以转化为求最大匹配用匈牙利算法解决。
1.最大匹配（边集）
此类问题最直接，直接用匈牙利算法即可。
HDU 2063 过山车
http://acm.hdu.edu.cn/showproblem.php?pid=2063
二分图最大匹配模版题。
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1654
易想到求最大独立集但是时间复杂度太高，可以变成二分图最大匹配来做，重在建模。
2.最小路径覆盖（边集）
对于不存在孤立的点的图，|最小路径覆盖|+|最大匹配|=V（顶点数）
因此可以通过求最大匹配来做。
这个等式在DAG图中也成立，详见http://www.cnblogs.com/jackiesteed/articles/2043934.html。对于DAG图可以拆点来做。
HDU 1151 Air Raid
http://acm.hdu.edu.cn/showproblem.php?pid=1151
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<vector>
#define MAXN 1005
using namespace std;
bool gl[MAXN][MAXN];
int link[MAXN];
int n;
bool vis[MAXN];
bool match(int x)
{
; i<=n; ++i)
if(gl[x][i]&&!vis[i])
{
vis[i]=true;
||match(link[i]))
{
link[i]=x;
return true;
}
}
return false;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{ int m;
scanf("%d%d",&n,&m);
memset(gl,,sizeof(gl));
;i<m;++i)
{
int x,y;
scanf("%d%d",&x,&y);
gl[x][y]=true;
}
;
memset(link,-,sizeof(link));
; i<=n; ++i)
{
memset(vis,,sizeof(vis));
if(match(i)) res++;
}
printf("%d\n",n-res);
}
;
}
求DAG的最小路径覆盖。
3.最小顶点覆盖（点集）
在二分图中|最大匹配|=|最小顶点覆盖|，但是注意要解决的问题本身并不是最大匹配，理解了问题本身才能建模。
HDU 1054 Strategic Game
http://acm.hdu.edu.cn/showproblem.php?pid=1054
此题可以用树形DP来做也可以用求最小顶点覆盖，但是时间较慢。拆点，改成双向图，用邻接表。
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<vector>
#define MAXN 1505
using namespace std;
vector<int> gl[MAXN];
int link[MAXN];
int n;
bool vis[MAXN];
void init()
{
memset(link,-,sizeof(link));
memset(vis,,sizeof(vis));
}
bool match(int x)
{
; i<gl[x].size(); ++i)
{
int &u=gl[x][i];
if(!vis[u])
{
vis[u]=true;
||match(link[u]))
{
link[u]=x;
return true;
}
}
}
return false;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(gl,,sizeof(gl));
; i<n; ++i) gl[i].clear();
; i<n; ++i)
{
int now,t,cn;
scanf("%d:",&now);
scanf("(%d)",&cn);
while(cn--)
{
scanf("%d",&t);
gl[now].push_back(t);
gl[t].push_back(now);
}
}
init();
;
; i<n; ++i)
{
memset(vis,,sizeof(vis));
if(match(i)) res++;
}
printf();
}
;
}
HDU 1150 Machine Schedule
http://acm.hdu.edu.cn/showproblem.php?pid=1150
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<vector>
#define MAXN 1005
using namespace std;
bool gl[MAXN][MAXN];
int link[MAXN];
int n,m;
bool vis[MAXN];
bool match(int x)
{
; i<=m; ++i)
if(gl[x][i]&&!vis[i])
{
vis[i]=true;
||match(link[i]))
{
link[i]=x;
return true;
}
}
return false;
}
int main()
{
int t;
while(scanf("%d",&n)&&n)
{
scanf("%d%d",&m,&t);
memset(gl,,sizeof(gl));
; i<t; ++i)
{
int x,y,z;
scanf("%d%d%d",&z,&x,&y);
gl[x][y]=true;
}
;
memset(link,-,sizeof(link));
; i<=n; ++i)
{
memset(vis,,sizeof(vis));
if(match(i)) res++;
}
printf("%d\n",res);
}
;
}
4.最大独立集（点集）
|最大独立集|+|最小顶点覆盖|=V
求最大独立集是NP问题，但是在二分图中|最大匹配|=|最小顶点覆盖|，所以这个问题也有了高效的算法。
HDU 1045 Fire Net
http://acm.hdu.edu.cn/showproblem.php?pid=1045
这个可以暴力求最大独立集。
HDU 2768 Cat vs. Dog
http://acm.hdu.edu.cn/showproblem.php?pid=2768
根据矛盾之间建图，求最大独立集。
HDU 1068 Girls and Boys
http://acm.hdu.edu.cn/showproblem.php?pid=1068
题意很明显就是求二分图最大独立集。但是由于没说给的是男还是女，所以需要拆点，得到的最大匹配数要除以2，再套用公式得最大独立集。
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<vector>
#define MAXN 1005
using namespace std;
bool gl[MAXN][MAXN];
int link[MAXN];
int n;
bool vis[MAXN];
void init()
{
memset(link,-,sizeof(link));
memset(vis,,sizeof(vis));
}
bool match(int x)
{
; i<n; ++i)
if(gl[x][i]&&!vis[i])
{
vis[i]=true;
||match(link[i]))
{
link[i]=x;
return true;
}
}
return false;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(gl,,sizeof(gl));
; i<n; ++i)
{
int now,t,cn;
scanf("%d: ",&now);
scanf("(%d) ",&cn);
while(cn--)
{
scanf("%d",&t);
gl[now][t]=true;
}
}
init();
;
; i<n; ++i)
{
memset(vis,,sizeof(vis));
if(match(i)) res++;
}
printf(-res)/);
}
;
}
5.判断二分图
此类问题可以BFS或DFS解决，注意图可能不连通。
HDU 4751 Divide Groups
http://acm.hdu.edu.cn/showproblem.php?pid=4751
根据不互相认识这一关系连边，判断二分图。