由于每行最多放一个，每列最多放一个（不能放置的位置不影响攻击，就是因为没注意这句话，把这题当做行列覆盖模型做了好久0.0）

所以把行列直接当做二分图X和Y集，可以放置的点的行列连边，求出的完备匹配就是第二个答案。

至于第一个答案求关键点，就枚举删除一条边能否任然得到完备匹配，若不行，则是关键点。

我的代码c++会WA，不知道为什么，求教啊。

#include
  
   
#include
   
     #include
    
      using namespace std; int mp[105][105]; int to[105]; bool vis[105]; int n; int dfs(int k) { for(int i=1;i<=n;i++) { if(!vis[i]&&mp[k][i]) { vis[i]=1; if(to[i]==-1||dfs(to[i])) { to[i]=k; return 1; } } } return 0; } int a[100090],b[100900]; int main() { int m,k,ca=1; while(scanf("%d%d%d",&n,&m,&k)!=EOF) { memset(mp,0,sizeof(mp)); for(int i=1;i<=k;i++) { scanf("%d%d",&a[i],&b[i]); mp[a[i]][b[i]]=1; } int ans=0; memset(to,-1,sizeof(to)); for(int i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); ans+=dfs(i); } int ans2=0,tot=0; for(int i=1;i<=k;i++) { ans2=0; mp[a[i]][b[i]]=0; memset(to,-1,sizeof(to)); for(int i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); ans2+=dfs(i); } if(ans2!=ans) tot++; mp[a[i]][b[i]]=1; } printf("Board %d have %d important blanks for %d chessmen.\n",ca++,tot,ans); } return 0; }