题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1281
题目大意：
每个车不能碰面，灰色不能放车，问最多可以放多少个车。关键的空位：如果这个位置不能放车的话。那么现在可以放的车的数量比之前少。


思路：最开始求最大匹配，然后枚举每一条边，拆了，最大匹配是否会减少？是，这就是关键边。

#include <bits/stdc++.h>
using namespace std;

int n,m, k, T=0;//顶点数n和边的数目m
int e[151][151];//保存一个无向图
int book[151];//每次都标记那个去了和那个没去
int match[151];//标记那个是匹配那个的
#define inf 9999//假设的无穷大
int dfs (int u)
{
    int i;
    for (i=1;i<=n;i++)
    {
        if (book[i]==0&&e[u][i]==1)//这个点在同一次上没去过，而且他们能联通
        {
            book[i]=1;//这个点已经尝试过了
            if (match[i]==0||dfs(match[i]))//这个点还没有被匹配，
                //或者，他可以匹配其他的人
            {
               //他们就能够匹配
                match[i]=u;//判断哪个，就是修改那个
        //match[u]=i;不用的，错误的
                return 1;
            }
        }
    }
    return 0;
}
int work ()
{
    memset(match, 0, sizeof(match));
    int i_count=0;
    for (int i=1;i<=n;i++)//尝试遍历每一个顶点
    {
        memset (book,0,sizeof(book));
        if (dfs(i))
        {
            i_count++;//若能找到新的匹配，就++
        }
    }

    return i_count;
}

int x[10100], y[10100];
int main ()
{
    while(~scanf("%d%d%d",&n,&m,&k))
    {
        T++;
        memset(e, 0, sizeof(e));
        for (int i=1;i<=k;i++)
        {
            int u,v;
            scanf ("%d%d",&x[i],&y[i]);

            e[x[i]][y[i]]=1;
        }
        int ans=work ();

        int cut=0;
        for(int i=1;i<=k;i++)
        {
            e[x[i]][y[i]]=0;

            if(ans!=work ())
            {
                cut++;
            }
            e[x[i]][y[i]]=1;
        }
        printf("Board %d have %d important blanks for %d chessmen.\n",T, cut, ans);
    }

    return 0;
}