POJ 2226 思维二分图

POJ 2226

背景： 此题在 POJ 3041基础上 需要将连续的点看做一个点

题意

  • 给出nxm的网格.有空地.和泥泞*.*求最少要用多少 (宽度为1的可伸长的木板) 覆盖所有的点**

思路

  • 因为木板长度可以任意伸长.所以无论是 行还是列,只要*连续就可以看成一个二分图中的点
  • 还是将行作为二分图的左部.列作为二分图的右部分.先求出原图每个点分别在左部分的编号和右部分的编号.
  • 等左右部分编完号后扫描原图一遍来建二分图.或者在求二分图右部分的编号时顺带建图
  • 求最大匹配.如何转化成二分图的最大匹配请先看POJ 3041思路
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn = 1e4;
char g[maxn][maxn];
int num[maxn][maxn],match[maxn],num1[maxn][maxn];
bool vis[maxn];
int n,m;
vector<int> e[maxn];

void read_() {
    for (int i=1; i<=n; ++i) {
        for (int j=1; j<=m; ++j)
            g[i][j] = getchar();
        getchar();
    }
}

int dfs(int u) {
    for (int i=0; i<e[u].size(); ++i) {
        int to = e[u][i];
        if (!vis[to]) {
            vis[to] = 1;
            if (!match[to] | dfs(match[to])) {
                match[to] = u;
                return 1;
            }
        }
    }
    return 0;
}

void solve() {
    int cnt_row=1;
    bool flag = 0;
    for (int i=1; i<=n; ++i) {
        for (int j=1; j<=m; ++j) {
            if (!flag && g[i][j]=='*')
                num[i][j] = cnt_row;
            else if (flag && g[i][j]=='*') {
                num[i][j] = ++cnt_row;
                flag = 0;
            }
            else
                flag=1;
        }
        if (!flag) flag=1;
    }
    int to;
    int cnt_col = 1;
    flag=0;
    for (int j=1; j<=m; ++j) {
        for (int i=1; i<=n; ++i) {
            if (!flag && g[i][j]=='*')
                num1[i][j] = cnt_col;
            else if (flag && g[i][j]=='*') {
                num1[i][j] = ++cnt_col;
                flag = 0;
            }
            else
                flag=1;
            // 可以在求右部分编号时顺便建图.也可以像底下一样重新扫描一遍来建图
            //if (num[i][j] && num1[i][j]) e[num[i][j]].push_back(num1[i][j]);
        }
        if (!flag) flag=1;
    }
    /*for (int i=1; i<=n; ++i) {*/
        //for (int j=1; j<=m; ++j)
            //cout <<"(" << num[i][j] << " " << num1[i][j] << ") ";
        //cout << "\n";
    /*}*/
    for (int i=1; i<=n; ++i)
        for (int j=1; j<=m; ++j)
            if (num[i][j] && num1[i][j])
                e[num[i][j]].push_back(num1[i][j]);

    int res = 0;
    for (int i=1; i<=cnt_row; ++i) {
        memset(vis,0,sizeof vis);
        if (dfs(i)) ++res;
    }
    cout << res << endl;
}
int main() {
    freopen("1.in","r",stdin);
    while (scanf("%d%d\n",&n,&m) != EOF) {
        read_();
        solve();
    }
    return 0;
}

算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！