Matrix
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3095 Accepted Submission(s): 1428
Problem Description
Give you a matrix(only contains 0 or 1),every time you can select a row or a column and delete all the '1' in this row or this column . Your task is to give out the minimum times of deleting all the '1' in the matrix.
Input
There are several test cases. The first line contains two integers n,m(1<=n,m<=100), n is the number of rows of the given matrix and m is the number of columns of the given matrix. The next n lines describe the matrix:each line contains m integer, which may be either ‘1’ or ‘0’. n=0 indicate the end of input.
Output
For each of the test cases, in the order given in the input, print one line containing the minimum times of deleting all the '1' in the matrix.
Sample Input
3 3 0 0 0 1 0 1 0 1 0 0
Sample Output
2
Author
Wendell
Source
Recommend
威士忌 | We have carefully selected several similar problems for you:
题目大意：
给你一个矩阵（只包含0或1），每次你可以选择一行或一列，并删除这一行或这个列中的所有“1”。您的任务是给出删除矩阵中所有“1”的最小时间。
思路：
这个题跟我们前面做的那个碰气球的题一样，是哪个题中的一小部分。
我们要将所有的1都删去，这就跟我们那个题中的我们选定一种颜色，将其全部消灭用的操作数。同样我们每一次只能对一行或者一列进行操作。这样我们对于1的位置的行与列连边，再把这两个（列和边）看作是两个集合。求它的最大匹配数。
一个很简单的二分图的板子。。
代码：
#include#include #include #include #include #define N 1500+10using namespace std;bool vis[N];int n,m,k,x,y,girl[N],map[N][N];int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f;}int find(int x){ for(int i=1;i<=m;i++) { if(!vis[i]&&map[x][i]) { vis[i]=true; if(girl[i]==-1||find(girl[i])) {girl[i]=x;return 1;} } } return 0;}int main(){ int t=0,sum,ans; while(1) { n=read();if(n==0) break; m=read(),ans=0; memset(map,0,sizeof(map)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { x=read(); if(x==1) map[i][j]=1; } memset(girl,-1,sizeof(girl)); for(int i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); if(find(i)) ans++; } printf("%d\n",ans); } return 0;}