题目：在保证尽量多的“车”的前提下，棋盘里有些格子是可以避开的，也就是说，不在这些格子上放车，也可以保证尽量多的“车”被放下。但是某些格子若不放子，就 无法保证放尽量多的“车”，这样的格子被称做重要点。Gardon想让小希算出有多少个这样的重要点，你能解决这个问题么？
二分图匹配居然还能这么用！！！脑洞大开啊！！！
思路：把棋盘的行x看成二分图左边的点，列y看成二分图右边的点，那么就把可以放车的位置看成是一条边，而二分图的最大匹配中x互不相同，y 互不相同，所以每个匹配都是不同行不同列，所以最大匹配就是最多可以放的车的数量。而要判断有多少个点是必须放的，只要在得出最大匹配后，每次去掉一个匹 配，再去运算看得出的结果是否与原来的最大匹配数相同，若相同就不是必须的，若不相同就是必须的。
Sample Input
3 3 4 //棋盘行列，可以放的位置数目
1 2 //位置坐标
1 3
2 1
2 2
3 3 4
1 2
1 3
2 1
3 2
Sample Output
Board 1 have 0 important blanks for 2 chessmen.
Board 2 have 3 important blanks for 3 chessmen.
#include<iostream>
#include<string.h>
#include<vector>
#include<cstdio>
using namespace std;
const int maxn = ;
int uN,vN;//u,v的数目，使用前面必须赋值
int g[maxn][maxn];//邻接矩阵
int linker[maxn];
bool used[maxn];
bool dfs(int u)
{
for(int v = ; v <=vN;v++) //注意编号
if(g[u][v] && !used[v])
{
used[v] = true;
if(linker[v] == - || dfs(linker[v]))
{
linker[v] = u;
return true;
}
}
return false;
}
int hungary()
{
int res = ;
memset(linker,-,sizeof(linker));
for(int u=;u <=uN;u++) //注意编号
{
memset(used,false,sizeof(used));
if(dfs(u))res++;
}
return res;
}
int main()
{
int n;
int i,j,k;
int ccase=;
freopen("1.in","r",stdin);
while(scanf("%d%d%d",&uN,&vN,&n)!=EOF)
{
memset(g,,sizeof(g));
ccase++;
int cnt=;
int p,q;
for(i=;i<n;i++)
{
scanf("%d%d",&p,&q);
g[p][q]=;
}
int ans=hungary();
for(i=;i<=uN;i++) //注意编号
{
for(j=;j<=vN;j++)
{
if(g[i][j]==)
{
g[i][j]=;
//printf("%d %d ***%d\n",i,j,hungary() );
if(ans>hungary()) cnt++;
g[i][j]=;
}
}
}
printf("Board %d have %d important blanks for %d chessmen.\n",ccase,cnt,ans);
}
return ;
}