HDU - 2119 Matrix （二分匹配）

逃离我推掉我的手 2022-05-17 12:05 125阅读 0赞

#                                                 Matrix #

### 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

### Sample Output ###

**题意描述：**

将一个只包含0或1的矩阵删除所有的1，每次可以选择一行或一列，能够删除这一行或一列的1，求删除所有1的最小次数。

**解题思路：**

二分匹配模板题求最大的匹配数，利用二分匹配求出最大匹配数即为删除所有1的最小次数。

#include<stdio.h>
    #include<string.h>
    int n,m;
    int e[110][110],book[110],match[110];
    int dfs(int u)
    {
    	int i;
    	for(i=1;i<=m;i++)
    	{
    		if(book[i]==0&&e[u][i]==1)
    		{
    			book[i]=1;
    			if(match[i]==0||dfs(match[i]))
    			{
    				match[i]=u;
    				return 1;
    			}
    		}
    	}
    	return 0;
    }
    int main()
    {
    	int i,j,sum;
    	while(scanf("%d",&n))
    	{
    		if(n==0)
    			break;
    		scanf("%d",&m);
    		for(i=1;i<=n;i++)
    			for(j=1;j<=m;j++)
    				scanf("%d",&e[i][j]);
    		memset(match,0,sizeof(match));
    		sum=0;
    		for(i=1;i<=n;i++)
    		{
    			memset(book,0,sizeof(book));
    			if(dfs(i))
    				sum++;
    		}
    		printf("%d\n",sum);
    	}
    	return 0;
    }