P3663 题解

· · 个人记录

前言

看过了题解，好像没有一篇纯粹的并查集解法。

本题写了一晚上，原因是对拍是造的数据一直出锅，话说这种题写 data 程序是真麻烦，简直就是什么时候 data 写完，什么时候宣告着你对拍结束。好像原本就是这样。

分析

我们了解一下问题：在一个二位矩阵中，规定哪些相邻的节点被阻断了“连通性”，我们需要寻找出每个连通块，并且将每个连通块中的每个点（牛）与除此以外其余连通块中的每个点一次相连，问总共能形成多少边。

我们的需求十分明显，即找出这些连通块，我们考虑每个连通块之间肯定不连通，即每个连通块直接肯定有相连的墙阻挡，再考虑并查集的作用，维护每个连通块中的每个点为一个父亲。我们进行合并操作，将每个点向他的上下左右四个方向连边，表示联通，而他不连通的条件就是他可能与上下左右点之间有墙，我们就不合并中间有墙的点。

如何判断中间有墙呢？我们观察到 n 的范围只有 100 ，所以我们把二维矩阵使用一维的数组表示，即第 i 行第 j 列的数的大小为 ： (i - 1) \times n + j 。这样，我们在输入的时候，把 r, c; \ r', c' 这两个点建一条“双向边”，考虑 n ^ 4 过大，我们使用空间较小的邻接表，合并的时候只需要判断一下该点是否与目标点“相连”即可。

我们再来想一下最后答案究竟怎么算，我们先枚举每个牛，找到他们的父亲节点，即代表他在哪个连通块，最后就能遍历出每个连通块中的牛数，使该连通块中的每头牛向其他连通块中的每头牛都连一条边， 即：sum_i * (m - sum_i)，对这个结果求和即可，但是我们发现每条边被 u 连了一遍，又被 v 连了一遍，所以显然是个“双向边”，我们在最后需要 ans / 2 。

还有一个小技巧，就是建边的时候只需要建右，下即可，因为我们是建的双向边，自己想一下就好了。

Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;
const int N = 201;

int ans,lyf;
int n, m, r;

int re() {
    int x = 0, f = 1;
    char ch = getchar();

    while (ch < '0'||ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    }

    while (ch <= '9'&&ch >= '0') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }

    return x * f;
}

int num;
int f[N * N];
int sum[N * N];
bool p[N * N];
bool vis[N][N];
queue <int> q;

int find (int x ){
    while (x != f[x])
    x = f[x] = f[f[x]];
    return x;
}

int wz(int x, int y) {
    return (x - 1) * n + y;
}

int dx[4] = {0, 1};
int dy[4] = {1, 0};

int cnt;
int head[N * N];

struct bal {
    int u, v;
    int nxt;
};
bal eg[N * N];

void add(int u, int v) {
    ++cnt; 
    eg[cnt].nxt = head[u];
    eg[cnt].u = u;
    eg[cnt].v = v;
    head[u] = cnt;
}

int main() {
//  freopen("data.in", "r", stdin);
//  freopen("baoli.out", "w", stdout);
    int x1, x2, y1, y2;
    n = re(); m = re(); r = re();

    for(int i = 1; i <= r; i++) {
        x1 = re(); y1 = re();
        x2 = re(); y2 = re();
        add(wz(x1, y1), wz(x2, y2));
        add(wz(x2, y2), wz(x1, y1));
    }

    for(int i = 1; i <= n * n; i++)
        f[i] = i;

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            int a = wz(i, j);
            for(int k = 0; k <= 1; k++) {
                x1 = i + dx[k];
                y1 = j + dy[k];
                if(x1 > n || y1 > n)
                    continue;

                int b = wz(x1, y1);
                bool flag = 0;

                for(int l = head[a]; l; l = eg[l].nxt) {
                    int v = eg[l].v;
                    if(v == b) {
                        flag = 1;
                        break;
                    }
                }

                if(flag) continue;

                int aa = find(a), bb = find(b);

                if(aa == bb) continue;

                f[bb] = aa;
            }
        }
    }

    for(int i = 1; i <= m; i++) {
        x1 = re(); y1 = re();

        if(vis[x1][y1]) continue;

        vis[x1][y1] = 1;
        int pos = find(wz(x1, y1));

        if(!p[pos])
            p[pos] = 1,q.push(pos);

        sum[pos] ++;
    }

    while (!q.empty()) {
        int x = q.front();  q.pop();
        ans += sum[x] * (m - sum[x]);
    }

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

    return  0;
}

/*
3 5 5
2 2 1 2
2 2 2 3
1 1 1 2
2 3 3 3 
3 2 3 3
3 3
2 2 
2 3
1 2
1 1
*/

扯淡

目前最优解是我！！！