hdoj--2119--Matrix(最小点覆盖)
2024-09-02 10:37:50
Matrix
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2319 Accepted Submission(s): 1030
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.
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.
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
给了一个n*m的矩阵,矩阵元素有0 1,每次可以消除一行或者一列的1,问最少多少次消除全部的1
最少点覆盖=最大匹配,匈牙利算法:
#include<stdio.h>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
vector<int>map[200];
int pipei[200],used[200];
int find(int x)
{
for(int i=0;i<map[x].size();i++)
{
int y=map[x][i];
if(!used[y])
{
used[y]=1;
if(!pipei[y]||find(pipei[y]))
{
pipei[y]=x;
return 1;
}
}
}
return 0;
}
int main()
{
int n,m;
while(scanf("%d",&n),n)
{
scanf("%d",&m);
for(int i=1;i<=n;i++)
{
map[i].clear();
pipei[i]=0;
}
int a;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&a);
if(a)
map[i].push_back(j);
}
}
int sum=0;
for(int i=1;i<=n;i++)
{
memset(used,0,sizeof(used));
sum+=find(i);
}
printf("%d\n",sum);
}
}
最新文章
- html/京东项目/京东网页高仿/js/jq/css/java web/
- Selenium Webdriver元素定位的常用方式
- error MSB6006: &ldquo;cmd.exe&rdquo;已退出,代码为 3。
- android获取系统通讯录
- 6.Android之switch和togglebutton按钮学习
- 关于去哪儿网的UI自动化测试脚本(Python实现)
- Quartz 多个触发器
- 多目标遗传算法 ------ NSGA-II (部分源码解析) 拥挤距离计算 crowddist.c
- HDU 4287 Intelligent IME
- 模拟DOMContentLoaded事件
- asp.net mvc 访问.html文件
- 深入理解JAVA的多态性[转]
- UNIX 网络编程知识,函数积累
- 使用Browserify来实现CommonJS的浏览器加载
- DOM4J熟知
- gvim 技巧
- jQuery -- 光阴似箭(二):jQuery效果的使用
- Laravel route ---- resoure
- 20165311 预备作业3 Linux安装及学习
- Oracle的卸载过程步骤
热门文章
- 在mac上截屏的几种方式
- Android_传感器光学
- SQL Server 检测到基于一致性的逻辑 I/O 错误 pageid 不正确(应为 1:1772,但实际为 0:0)。在文件 &#39;D:\Program Files\Microsoft SQL Ser
- Pull-up resistors
- jQuery中容易让人困惑的东西
- dubbo之负载均衡
- 用一条mysql语句插入多条数据
- List集合的特有功能概述和测试
- day001 Python 计算机基础(2019年5月16日)
- PAT_A1144#The Missing Number