题目来源：https://vjudge.net/problem/HDU-1281
题意
在n*m的棋盘上，有k个空位置，只能放一种棋，叫做車，并且使得他们不能互相攻击到彼此，问，最多能放多少个車，而且，有一个点被这样定义：若是这个点不能放車，使得匹配数小于最大匹配数，那么叫做关键点，问有多少个关键点、
思路
以x,y坐标进行二分匹配，因为不能相互攻击，所以每个x,y坐标只能够使用一次，所以这就成了二分图匹配，而且，问关键点，那么就一个一个 枚举可以放車的位置，然后标记一下使得他不能放車，再进行二分匹配。
代码
#include<cstdio>
#include<vector>
#include<map>
#include<stack>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,k;
int relax[
110][
110];
int parent[
110];
int vis[
110];
bool dfs(
int x)
{
for(
int i=
1;i<=m;i++)
{
if(relax[x][i]&&!vis[i])
{
vis[i]=
1;
if(!parent[i]||dfs(parent[i]))
{
vis[i]=
0;
parent[i]=x;
return 1;
}
}
}
return 0;
}
int deal()
{
int num=
0;
memset(parent,
0,
sizeof(parent));
memset(vis,
0,
sizeof(vis));
for(
int i=
1;i<=n;i++)
{
if(dfs(i))
{
num++;
}
}
return num;
}
int main()
{
int cases=
0;
while(~
scanf(
"%d%d%d",&n,&m,&k))
{
int x,y;
memset(relax,
0,
sizeof(relax));
for(
int i=
1;i<=k;i++)
{
scanf(
"%d%d",&x,&y);
relax[x][y]=
1;
}
int tmp=deal();
int ans=
0;
for(
int i=
1;i<=n;i++)
{
for(
int j=
1;j<=m;j++)
{
if(relax[i][j])
{
relax[i][j]=
0;
int res=deal();
if(res<tmp)
{
ans++;
}
relax[i][j]=
1;
}
}
}
printf(
"Board %d have %d important blanks for %d chessmen.\n",++cases,ans,tmp);
}
}
