HDU 1281 棋盘游戏(二分图最大匹配+枚举删边)

#include <bits/stdc++.h>
#define maxn 205
using namespace std;
int edge[maxn][maxn];
int pre[maxn];
bool vis[maxn];
int x[maxn], y[maxn];
int n,m,k;

bool dfs(int x){
  for(int i=1;i<=m;i++){
    if(vis[i] == false && edge[x][i]){
      vis[i] = true;
      if(pre[i] == -1 || dfs(pre[i])){
        pre[i] = x;
        return true;
      }
    }
  }
  return false;
}

int main()
{
  int Case = 1;
  while(~scanf("%d%d%d",&n,&m,&k)){
    memset(edge,0,sizeof(edge));
    for(int i=1;i<=k;i++){
      scanf("%d%d",&x[i],&y[i]);
      edge[ x[i] ][ y[i] ] = 1;
    }
    int ans = 0;
    int cnt = 0;
    memset(pre,-1,sizeof(pre));
    for(int i=1;i<=n;i++){
      memset(vis,false,sizeof(vis));
      if(dfs(i)) ans ++;
    }
    for(int i=1;i<=k;i++){
      edge[ x[i] ][ y[i] ] = 0;
      memset(pre,-1,sizeof(pre));
      int ans1 = 0;
      for(int j=1;j<=n;j++){
        memset(vis,false,sizeof(vis));
        if(dfs(j)) ans1 ++;
      }
      if(ans1 != ans) cnt ++;
      edge[ x[i] ][ y[i] ] = 1;
    }
    printf("Board %d have %d important blanks for %d chessmen.\n",Case++,cnt,ans);
  }
  return 0;
}