裸的匹配题，一眼就能看出来二分图的模型，是某个经典题的改编。貌似某本图论书上讲过的，有N个人以及M个职位，每个职位只能提供给一个人，而每个人由于能力有限只能胜任有限个职位，问是否有办法使得每个人都有工作，如果不能，最多能给多少个人提供工作。如果看过这道经典题的话，这题的思路就顺秒了：将n道题看成n个点属于二分图的x部，将m个锦囊看成m个点属于y部，用匈牙利算法做这个二部图的匹配，当某个点不能匹配时算法结束
值的一说的是，由于这个二部图的特性，x部每个点有且仅有2条边与y部相连，利用这个特性能够大大优化这个算法（下面这个程序属于无脑敲的匈牙利，没用这个优化。。。。竟然也能过）
#include<iostream>
#include<cstdio>
#include <math.h>
#include <string.h>
using namespace std;
intmatch[1009],visit[1009]={0},n,map[1009][1009]={0};
int dfs(int k)
{
for (int i=0;i<=n-1;i++)
{
if (map[k][i]==1 && visit[i]==0)
{
visit[i]=1;
if ((match[i]==-1) || (dfs(match[i])==1))
{
match[i]=k;
return 1;
}
}
}
return 0;
}
int main()
{
int m,ans=0,x,y;
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
map[i][x]=1;
map[i][y]=1;
}
memset(match,255,sizeof(match));
for (inti=1;i<=m;i++)
{
memset(visit,0,sizeof(visit));
if (dfs(i)==1)ans++;else break;
}
printf("%d",ans);
scanf("%d%d",&n,&m);
return0;
}
BZOJ 1191: [HNOI2006]超级英雄Hero【二分图匹配】
原文：http://www.cnblogs.com/philippica/p/4006944.html