【并查集】【环】jzoj3809. 【NOIP2014模拟8.25】设备塔-白红宇

【并查集】【环】jzoj3809. 【NOIP2014模拟8.25】设备塔

阅读量：362 次

发布时间：2019-03-04

本文共 2670 字，大约阅读时间需要 8 分钟。

为了解决这个问题，我们需要确保在改造设备塔的区块时，不会断开数据通道，使得设备塔的两端无法连通。我们可以使用并查集（Union-Find）数据结构来高效地管理各个区块的连通性。

方法思路

初始化并查集：每个区块初始时不与任何其他区块连通。

处理每个操作：对于每个要改造的区块，检查该区块及其周围八个相邻区块中的改造区块。

判断连通性：如果在这些区块中存在至少一个连通到圆柱体两端的区块，那么这个操作是可行的。

执行操作：将相关区块标记为改造，并更新并查集。

统计可行操作：统计所有可行操作的数量。

解决代码

#include 
   
    int n, m, k;int fx[8] = { -2*m-1, -2*m, -2*m+1, -1, 1, 2*m-1, 2*m, 2*m+1 };int B[200001] = {0};int f[200001];int find(int d) {    if (f[d] == 0 || f[d] == d) return d;    return f[d] = find(f[d]);}int main() {    scanf("%d%d%d", &n, &m, &k);    for (int i = 1; i <= k; ++i) {        int a, b;        scanf("%d%d", &a, &b);        int l1bh = (a-1) * 2 * m + b;        int l2bh = l1bh + m;        int pd = 0;        for (int ii = 0; ii < 8 && pd == 0; ++ii) {            int bh1 = l1bh + fx[ii];            if ((l1bh - 1) % (2 * m) == 0) {                if (ii == 0) bh1 = l1bh - 1;                if (ii == 3) bh1 = l1bh + 2 * m - 1;                if (ii == 5) bh1 = l1bh + 4 * m - 1;            }            if (bh1 > 0 && bh1 <= 2 * n * m) {                if (B[bh1] == 1) {                    for (int j = 0; j < 8; ++j) {                        int bh2 = l2bh + fx[j];                        if (l2bh % (2 * m) == 0) {                            if (j == 2) bh2 = l2bh - 4 * m + 1;                            if (j == 4) bh2 = l2bh - 2 * m + 1;                            if (j == 7) bh2 = l2bh + 1;                        }                        if (bh2 > 0 && bh2 <= 2 * n * m) {                            if (B[bh2] == 1) {                                if (find(bh1) == find(bh2)) {                                    pd = 1;                                    break;                                }                            }                        }                    }                }            }        }        if (pd == 0) {            ++Ans;            B[l1bh] = B[l2bh] = 1;            for (int j = 0; j < 8; ++j) {                int bh1 = l1bh + fx[j];                if ((l1bh - 1) % (2 * m) == 0) {                    if (j == 0) bh1 = l1bh - 1;                    if (j == 3) bh1 = l1bh + 2 * m - 1;                    if (j == 5) bh1 = l1bh + 4 * m - 1;                }                if (bh1 > 0 && bh1 <= 2 * n * m) {                    if (B[bh1] == 1) {                        int root1 = find(l1bh);                        int root2 = find(bh1);                        f[root1] = root2;                    }                }            }        }    }    printf("%d", Ans);}