poj 2226(二分图最小顶点覆盖)

poj 2226
题意:用宽度为1长度不限的木板将 * 盖住而不盖住 .

我们考虑二分图中一条边为一个点。我们对横竖进行遍历,看只横和只竖所需要的木板并且标号,例如样例

1
2
3
4
5
4 4
*.*.
.***
***.
..*.

横着:(图中数字表示用的是第几块木板)

1
2
3
4
1.2.
.333
444.
..5.

竖着:

1
2
3
4
1.4.
.345
234.
..4.

我们发现每一个点都可以被两块方向不同的木板覆盖,所以就以这个为依据建边,边相当于一个点,那么只要求出最小顶点覆盖即可。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
int r, c;
char map[100][100];
int hang[100][100], lie[100][100], sz_hang = 0, sz_lie = 0;
vector<int> G[3000];
int lk[3000], vis[3000], cnt;
bool hungary(int u) {
for (int i = 0; i < (int)G[u].size(); i++) {
int v = G[u][i];
if (vis[v] != cnt) {
vis[v] = cnt;
if (!lk[v] || hungary(lk[v])) {
lk[v] = u;
return true;
}
}
}
return false;
}
void clean() {
ms(lk, 0), ms(vis, 0), ms(hang, 0), ms(lie, 0);
}
int solve() {
clean();
for (int i = 1; i <= c; i++) map[0][i] = '\0';
for (int i = 1; i <= r; i++) scanf("%s", map[i] + 1), map[i][0] = '\0';
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
if (map[i][j] == '*' && map[i][j - 1] != '*') hang[i][j] = ++sz_hang;
if (map[i][j] == '*' && map[i][j - 1] == '*') hang[i][j] = hang[i][j - 1];
}
}
for (int i = 1; i <= c; i++) {
for (int j = 1; j <= r; j++) {
if (map[j][i] == '*' && map[j - 1][i] != '*') lie[j][i] = ++sz_lie;
if (map[j][i] == '*' && map[j - 1][i] == '*') lie[j][i] = lie[j - 1][i];
}
}
for (int i = 1; i <= r; i++)
for (int j = 1; j <= c; j++) G[hang[i][j]].push_back(lie[i][j]);
int ans = 0;
for (int i = 1; i <= sz_hang; i++) ans += hungary(cnt = i);
printf("%d", ans);
return 0;
}
int main() {
scanf("%d%d", &r, &c), solve();
return 0;
}
------ 本文结束 ------