棋盘游戏 HDU1281

一开始毫无思路  看了题解才发现是二分图的最大匹配问题

行为n 列为m  行列匹配  （一行只能与一列匹配   这点和象棋的车的意义一样）

再去掉点看看最大匹配会不会少  如果少了说明为关键点

其中  x，y数组值得学习！

#include<bits/stdc++.h>

using namespace std;

#define MAXI 105

int mp[MAXI][MAXI];

int used[MAXI];

int vis[MAXI];

int n,m;

bool dfs(int  x)

{

    for(int j=;j<=m;j++)

    {

        if(mp[x][j]&&!used[j])

        {

            used[j]=;

            if(!vis[j]||dfs(vis[j]))

              {

                  vis[j]=x;

                  return true;

              }

        }

    }

    return false;

}

int find1(void)

{    int ans=;

 memset(vis,,sizeof(vis));

     for(int i=;i<=n;i++)

       {

           memset(used,,sizeof(used));

           if(dfs(i))ans++;

       }

       return ans;

}

int main()

{

   int k;

   int cas=;

   while(scanf("%d%d%d",&n,&m,&k)==)

   {

       memset(mp,,sizeof(mp));

       int x[MAXI*MAXI],y[MAXI*MAXI];

      for(int i=;i<=k;i++)

      {

          scanf("%d%d",&x[i],&y[i]);

          mp[ x[i] ][ y[i] ]=;

      }

       int ans=find1();

       int sum=;

       for(int i=;i<=k;i++)

       {

           mp[ x[i] ][ y[i] ]=;

           int a=find1();

           if(a<ans) sum++;

           mp[ x[i] ][ y[i] ]=;

       }

      printf("Board %d have %d important blanks for %d chessmen.\n",++cas,sum,ans);

   }

}

做了1045感觉有点疑惑

发现这种是   没有障碍的   只是限定哪些格子可以放

而那题有墙这种概念