将每一行/每一列作为一个点，对于一个障碍(x,y)，要么第x行和第y列的状态（是否攻击）只需要有一个就可以了，将第x行和第y列连边，就是二分图的最小点覆盖=最大匹配数。

1 #include
      
        2 using namespace std; 3 #define N 1005 4 struct ji{ 5     int nex,to; 6 }edge[N*20]; 7 int E,n,m,x,y,ans,head[N],flag[N],vis[N]; 8 void add(int x,int y){ 9     edge[E].nex=head[x];10     edge[E].to=y;11     head[x]=E++;12 }13 int dfs(int k){14     if (vis[k])return 0;15     vis[k]=1;16     for(int i=head[k];i!=-1;i=edge[i].nex){17         int v=edge[i].to;18         if ((!flag[v])||(dfs(flag[v]))){19             flag[v]=k;20             flag[k]=v;21             return 1;22         }23     }24     return 0;25 }26 int main(){27     scanf("%d%d",&n,&m);28     memset(head,-1,sizeof(head));29     for(int i=1;i<=m;i++){30         scanf("%d%d",&x,&y);31         add(x,y+n);32         add(y+n,x);33     }34     for(int i=1;i<=n;i++){35         memset(vis,0,sizeof(vis));36         if (!flag[i])ans+=dfs(i);37     }38     printf("%d",ans);39 }