HDU - 2119 Matrix

Matrix

Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3788 Accepted Submission(s): 1803

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
HDU 2007-10 Programming Contest_WarmUp

二分图的最小点覆盖。

我们把横，竖分别看成点，然后如果某个点为1，就将横竖连起来。

最后看最小点覆盖（也就是最大匹配数）。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1010,M=2e4+10;
int n,m,mat[N],vis[N],res;
int head[N],nex[M],to[M],tot;
inline void add(int a,int b){
	to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
int find(int x){
	for(int i=head[x];i;i=nex[i]){
		if(vis[to[i]])	continue;
		vis[to[i]]=1;
		if(!mat[to[i]]||find(mat[to[i]])){
			mat[to[i]]=x;	return 1;
		}
	}
	return 0;
}
signed main(){
	while(cin>>n,n){
		cin>>m;	tot=0;	memset(head,0,sizeof head);
		memset(mat,0,sizeof mat);	res=0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				int x;	scanf("%d",&x);	if(x)	add(i,j);
			}
		}
		for(int i=1;i<=n;i++){
			memset(vis,0,sizeof vis);	
			if(find(i))	res++;
		}
		cout<<res<<endl;
	}
	return 0;
}