题目链接：

题意很好理解，就是每次可以删除一行或者一列数，问最少几次可以把所有的1都变成0，也就是都删完。

利用二分图解

行表示二分图的一部分,列表示一部分,为1的点表示连一条边,然后求最小顶点覆盖数。

最小顶点覆盖即表示用最少的顶点把所有的边都关联到。

最小顶点覆盖 = 最大匹配。

 

此外二分图还有最小路径覆盖,意思是用最少的边把图中所有的顶点都遍历到。

最小路径覆盖 = 顶点数 - 最大匹配。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 using namespace std; 5 const int MAX=105; 6 int map[MAX][MAX]; 7 int visit[MAX]; 8 int use[MAX]; 9 int n,m;10 int solve(int x)11 {12     int j;13     for(j=1;j<=m;j++)14     {15         if(map[x][j]&&!visit[j])16         {17             visit[j]=1;18             if(use[j]==-1||solve(use[j]))19             {20                 use[j]=x;21                 return 1;22             }23         }24     }25     return 0;26 }27 int match()28 {29     int i,count=0;30     for(i=1;i<=n;i++)31     {32         memset(visit,0,sizeof(visit));33         if(solve(i))count++;34     }35     return count;36 }37 int main()38 {39     int x,i,j;40     while(scanf("%d",&n)&&n)41     {42         memset(use,-1,sizeof(use));43         memset(map,0,sizeof(map));44 45         scanf("%d",&m);46         for(i=1;i<=n;i++)47         for(j=1;j<=m;j++)48         {49             scanf("%d",&x);50             if(x)  map[i][j]=1;51         }52         x=match();53         printf("%d\n",x);54     }55     return 0;56 }