某程笔试T2,最小点覆盖

Posted by Cww97 on 2018-03-29

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/79748608
## 题意:

N*M 01矩阵,每次可以删去一行或者一列,问删去所有的1最少操作次数

emmm

poj3041原题
二分图,行当成一个点放左边,列当成一个点放右边
即求最小点覆盖 == 最大匹配

好久不做题脑子快生锈了

code

好多人吐槽这vector的格式

不知道用自己写的板子算不算作弊

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
using namespace std;
const int N = 1111;

struct Hungary{
vector <int> G[N];
bool used[N];
int girl[N], n, m;

inline void init(int _n, int _m){
n = _n, m = _m;
for (int i = 0; i <= n; i++) G[i].clear();
}

inline void addEdge(const int &u, const int &v){
G[u].push_back(v);
}

bool Find(int x){
for (int i = 0; i < G[x].size(); i++){
int j = G[x][i];
if (used[j]) continue;
used[j] = 1;
if (girl[j] == -1 || Find(girl[j])) {
girl[j] = x;
return true;
}
}
return false;
}

inline int hungary(const int &n, const int &m){
int all = 0;
memset(girl, -1, sizeof girl);
for (int i = 0; i < n; i++) {
memset(used, 0, sizeof(used)); //这个在每一步中清空
if (Find(i)) all += 1;
}
//for (int i = 0; i < m; i++) printf("girl[%d] = %d\n", i, girl[i]);
//printf("all = %d\n", all);
return all;
}
} hg;

int calculate(int rows, int cols, vector < vector < int > > matrix) {
hg.init(rows, cols);
for (int i = 0; i < rows; i++){
for (int j = 0; j < cols; j++){
if (matrix[i][j]) hg.addEdge(i, j);
}
}
int match = hg.hungary(rows, cols);
//printf("%d\n", match);
//int ans = rows + cols - match;
return match;
}
/******************************结束写代码******************************/

int main() {
//freopen("in.txt", "r", stdin);
int res;
int _matrix_rows = 0;
int _matrix_cols = 0;
cin >> _matrix_rows >> _matrix_cols;
vector< vector < int > > _matrix(_matrix_rows);
for(int _matrix_i=0; _matrix_i<_matrix_rows; _matrix_i++) {
for(int _matrix_j=0; _matrix_j<_matrix_cols; _matrix_j++) {
int _matrix_tmp;
cin >> _matrix_tmp;
_matrix[_matrix_i].push_back(_matrix_tmp);
}
}

res = calculate(_matrix_rows, _matrix_cols, _matrix);
cout << res << endl;
return 0;
}