【题意】给定n*n网格，有k个物品，每次可以消灭一行或一列，求消灭掉所有物品的最少操作次数。

【算法】二分图最小覆盖

【题解】此题是最小覆盖模型的出处。

将物品的x-y连边建立二分图。

最小覆盖：选择最少的点，使每条边至少有一个端点被覆盖。

刚好对应题意。

最小覆盖可以用最小割解决，将选择点视为割去边，S-T不连通就是边至少一个点被覆盖。

注意：二分图开双倍点。

#include
      
       #include
       
        #include
        
          #include
         
          using namespace std;const int maxn=20010,inf=0x3f3f3f3f;//2*int tot=1,first[maxn],cur[maxn],d[maxn],S,T,n,k;//tot=1queue
          
           q;struct edge{
    int v,flow,from;}e[maxn*10];void insert(int u,int v){    tot++;e[tot].v=v;e[tot].flow=1;e[tot].from=first[u];first[u]=tot;    tot++;e[tot].v=u;e[tot].flow=0;e[tot].from=first[v];first[v]=tot;}bool bfs(){    memset(d,-1,sizeof(d));    d[S]=0;q.push(S);    while(!q.empty()){        int x=q.front();q.pop();        for(int i=first[x];i;i=e[i].from)if(e[i].flow&&d[e[i].v]==-1){            d[e[i].v]=d[x]+1;            q.push(e[i].v);        }    }    return d[T]!=-1;}int dinic(int x,int a){    if(x==T||a==0)return a;    int flow=0,f;    for(int &i=cur[x];i;i=e[i].from)    if(e[i].flow&&d[e[i].v]==d[x]+1&&(f=dinic(e[i].v,min(a,e[i].flow)))>0){        e[i].flow-=f;        e[i^1].flow+=f;        a-=f;        flow+=f;        if(a==0)break;    }    return flow;}int main(){    scanf("%d%d",&n,&k);    int u,v;    S=0;T=n+n+1;    for(int i=1;i<=k;i++){        scanf("%d%d",&u,&v);        insert(u,v+n);    }    for(int i=1;i<=n;i++){insert(S,i);insert(i+n,T);}    int ans=0;    while(bfs()){        for(int i=S;i<=T;i++)cur[i]=first[i];//S-T        ans+=dinic(S,inf);    }    printf("%d",ans);    return 0;}