一开始毫无思路 看了题解才发现是二分图的最大匹配问题
行为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=1;j<=m;j++) { if(mp[x][j]&&!used[j]) { used[j]=1; if(!vis[j]||dfs(vis[j])) { vis[j]=x; return true; } } } return false; } int find1(void) { int ans=0; memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) { memset(used,0,sizeof(used)); if(dfs(i))ans++; } return ans; } int main() { int k; int cas=0; while(scanf("%d%d%d",&n,&m,&k)==3) { memset(mp,0,sizeof(mp)); int x[MAXI*MAXI],y[MAXI*MAXI]; for(int i=1;i<=k;i++) { scanf("%d%d",&x[i],&y[i]); mp[ x[i] ][ y[i] ]=1; } int ans=find1(); int sum=0; for(int i=1;i<=k;i++) { mp[ x[i] ][ y[i] ]=0; int a=find1(); if(a<ans) sum++; mp[ x[i] ][ y[i] ]=1; } printf("Board %d have %d important blanks for %d chessmen. ",++cas,sum,ans); } }
做了1045感觉有点疑惑
发现这种是 没有障碍的 只是限定哪些格子可以放
而那题有墙这种概念