Codeforces Round #375 (Div. 2) D. Lakes in Berland 并查集

http://codeforces.com/contest/723/problem/D

这题是只能把小河填了，题目那里有写，其实如果读懂题这题是挺简单的，预处理出每一块的大小，排好序，从小到大填就行了。

以前找这些块的个数用的是dfs。现在这次用并查集做下。

首先要解决的是，二维坐标怎么并查集，以前的并查集都是一维的，现在是两个参数，那么就考虑离散，每对应一个点，离散到一个独特的一维数值即可。我用的公式的50 * x + y。这样得到的数值是唯一的。所以可以快乐地并查集了。

那么遇到一个'.'，我们需要它和其他合并，思路就是观察其上面和左边是否存在'.'，如果存在，就合并到左边（上面），没有，那就是自己一个块了。

有顺序的，检查完上面，合并完（现在爸爸是上面那个），还要检查左边，如果有，左边的就要合并过来。这样爸爸就只是上面那个了。

为什么要这样做呢？因为考虑下这个

***.**

*. ..**

枚举到加粗那个的时候，如果你只向左合并，则遗漏了上面那个，向上合并，又会使得左边的被算作不同的块。GG

所以是需要两边判断，同时合并的。注意合并的方向是固定的，需要及时选择那个是爸爸

然后就是排序删除了，每个点的爸爸是固定的，用个标记数组标记下删除了那个爸爸，输出的时候对应一下就好

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

const int maxn =  * ;

char str[ + ][ + ];

int fa[maxn];

LL size[maxn];

int calc(int x, int y) {

    return  * x + y;

}

int find(int x) {

    if (fa[x] == x) return x;

    else return fa[x] = find(fa[x]);

}

void merge(int x, int y) {

    x = find(x);

    y = find(y);

    if (x != y) {

        fa[y] = x;

        size[x] += size[y];

    }

}

int del[maxn];

struct node {

    LL size;

    int FA;

    bool operator < (const struct node &rhs) const {

        return size < rhs.size;

    }

    node(LL aa, int bb) : size(aa), FA(bb) {}

};

multiset<struct node>ss;

bool used[maxn];

void work() {

    int n, m, k;

    scanf("%d%d%d", &n, &m, &k);

    for (int i = ; i <= n; ++i) {

        scanf("%s", str[i] + );

    }

    for (int i = ; i <= maxn - ; ++i) {

        size[i] = ;

        fa[i] = i;

    }

    for (int i = ; i <= n; ++i) {

        size[calc(i, )] = inf;

        size[calc(i, m)] = inf;

    }

    for (int i = ; i <= m; ++i) {

        size[calc(, i)] = inf;

        size[calc(n, i)] = inf;

    }

    for (int i = ; i <= n; ++i) {

        for (int j = ; j <= m; ++j) {

            if (str[i][j] == '.') {

                if (str[i - ][j] == '.' && i -  >= ) {

                    merge(calc(i - , j), calc(i, j));

                }

                if (str[i][j - ] == '.' && j -  >= ) merge(calc(i, j), calc(i, j - ));

            }

        }

    }

    for (int i = ; i <= n; ++i) {

        for (int j = ; j <= m; ++j) {

            if (str[i][j] == '*') continue;

            int FA = find(calc(i, j));

            if (used[FA]) continue;

            if (size[FA] >= inf) continue;

            ss.insert(node(size[FA], FA));

            used[FA] = ;

        }

    }

    multiset<struct node> :: iterator it = ss.begin();

    int cut = ss.size() - k;

    int ans = ;

    while (cut--) {

        del[it->FA] = ;

        ans += size[it->FA];

        it++;

    }

    printf("%d\n", ans);

    for (int i = ; i <= n; ++i) {

        for (int j = ; j <= m; ++j) {

            int FA = find(calc(i, j));

            if (del[FA]) {

                printf("*");

            } else printf("%c", str[i][j]);

        }

        printf("\n");

    }

}

int main() {

#ifdef local

    freopen("data.txt","r",stdin);

#endif

    work();

    return ;

}

巴特西

Codeforces Round #375 (Div. 2) D. Lakes in Berland 并查集

最新文章

热门文章