加载中...
题解 P1173 【[NOI2016]网格】

前言

这个码量绝对是业界大毒瘤……

$300$行,$6.5$k,烦的要死……

正文

题意:

给你一个网格图,里面有$0$或$1$。你需要把一些$0$换成$1$使得存在某两个$0$不四联通。输出最小的换的数量。无解$-1$。

$n,m\leq10^8$,网格中1的数量$\leq10^4$,多组数据。

首先我们发现,最多只要$2$就行了(围住一个角落),所以答案是$[-1,2]$中的整数。

然后考虑何时为$-1$:$0$的数目小于$2$或等于$2$且相连。

何时为$0$:图初始就不连通。

何时为$1$:图中存在割点。

除此之外就是$2$了。

然后发现图很大,$c$很小,考虑离散化。

然后发现我们只要把每个$1$周围的点提取出来即可。

提取$3\times 3$是错误的,有个众人皆知的样例:

0 0 0
0 0 0
0 0 1

显然提取之后会有一个割点在原图正中间,但是实际上它并不是割点。

然后我们暴力一点,提取$5\times5$即可……

算法流程:提取点,编号。然后判断联通性。然后做tarjan,判断割点。

然后又有好多坑点…比如割点必须在某个$1$的周围$3\times3$区域(易证),如果忽视这个就会出现一种毒瘤情况:

1 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 1

可以发现在奇怪的地方出现了割点…

然后还要特判,$(n - 1)(m - 1) = 0$的时候答案不可能为$2$。

然后怒写一天半终于对了,又发现map太慢跑不过……手写hash。

终于A了….然后uoj日常97分……

$update$:如何判断答案为$0$:对那些提取出来的非关键点进行并查集。然后枚举每个关键点连通块,如果某个关键点连通块连着两个并查集,答案为$0$。

代码:

#include <cstdio>
#include <algorithm>
#include <cstring>

inline void read(int &x) {
    x = 0;
    char c = getchar();
    while(c < '0' || c > '9') {
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + c - 48;
        c = getchar();
    }
    return;
}

const int N = 100010;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};

const int MO = 19260817, B = 998244353;
struct POS {
    int x, y, h;
    POS(int xx = 0, int yy = 0) {
        x = xx;
        y = yy;
        h = (1ll * x * B + y) % MO;
        if(h < 0) {
            h += MO;
        }
    }
    inline bool operator ==(const POS &d) const {
        return x == d.x && y == d.y;
    }
};
struct Node {
    int nex, val;
    POS p;
}node[N * 30]; int top;
struct MAP {
    int e[MO];
    inline void insert(const POS &d, const int &a) {
        node[++top].val = a;
        node[top].nex = e[d.h];
        node[top].p = d;
        e[d.h] = top;
        return;
    }
    inline int find(const POS &d) { // if not exist  return 0
        for(int i = e[d.h]; i; i = node[i].nex) {
            if(node[i].p == d) {
                return node[i].val;
            }
        }
        return 0;
    }
    inline void clear() {
        memset(e, 0, sizeof(e));
        return;
    }
}mp, use;

int n, m, c, xi[N], yi[N], tot, num, root;
int dfn[N * 25], low[N * 25], vis[N * 25];
bool cut[N * 25], vis_c[N], OK;

inline void np(int x, int y) {
    if(!mp.find(POS(x, y)) && !use.find(POS(x, y))) {
        mp.insert(POS(x, y), ++tot);
    }
    return;
}

inline int get(int x, int y) {
    return mp.find(POS(x, y));
}

void tarjan(int s, int x, int y) {
    dfn[s] = low[s] = ++num;
    int temp = 0;
    for(int i = 0; i < 4; i++) {
        int t = get(x + dx[i], y + dy[i]);
        if(!t) {
            continue;
        }
        if(!dfn[t]) {
            tarjan(t, x + dx[i], y + dy[i]);
            low[s] = std::min(low[s], low[t]);
            if(low[t] >= dfn[s]) {
                temp++;
            }
        }
        else {
            low[s] = std::min(low[s], dfn[t]);
        }
    }
    if(temp >= 2 || (temp == 1 && s != root)) {
        cut[s] = 1;
    }
    return;
}

void DFS_1(int s, int x, int y, int temp) {
    vis[s] = temp;
    for(int i = 0;i < 4; i++) {
        int t = get(x + dx[i], y + dy[i]);
        if(!t) {
            continue;
        }
        if(!vis[t]) {
            DFS_1(t, x + dx[i], y + dy[i], temp);
        }
    }
    return;
}

bool fd;
int number;

bool DFS_2(int s, int x, int y) {
    vis_c[s] = 1;
    for(int i = 0; i < 4; i++) {
        if(use.find(POS(x + dx[i], y + dy[i]))) {
            int ed = use.find(POS(x + dx[i], y + dy[i]));
            if(vis_c[ed]) {
                continue;
            }
            int t = DFS_2(ed, x + dx[i], y + dy[i]);
            if(!t) {
                return 0;
            }
        }
        else if(get(x + dx[i], y + dy[i])) {
            if(!fd) {
                number = vis[get(x + dx[i], y + dy[i])];
                fd = 1;
            }
            else if(number != vis[get(x + dx[i], y + dy[i])]) {
                OK = 0;
                return 0;
            }
        }
    }
    return 1;
}

inline bool check() {
    OK = 1;
    int temp = 0;
    for(int i = 1; i <= c; i++) {
        for(int x = xi[i] - 2; x <= xi[i] + 2; x++) {
            for(int y = yi[i] - 2; y <= yi[i] + 2; y++) {
                if(vis_c[i]) {
                    continue;
                }
                if(mp.find(POS(x, y)) && !vis[get(x, y)]) {
                    ++temp;
                    DFS_1(get(x, y), x, y, temp);
                    goto f1;
                }
            }
        }
        f1:
        if(!vis_c[i]) {
            fd = 0;
            DFS_2(i, xi[i], yi[i]);
        }
        if(!OK) {
            break;
        }
    }
    return !OK;
}

inline int solve() {
    read(n);
    read(m);
    read(c);
    if(!c) {
        if(n == 1 && m == 1) {
            return -1;
        }
        if(n == 1 || m == 1) {
            if(n == 2 || m == 2) {
                return -1;
            }
            return 1;
        }
        return 2;
    }
    for(int i = 1; i <= c; i++) {
        read(xi[i]);
        read(yi[i]);
        use.insert(POS(xi[i], yi[i]), i);
    }
    if(c + 1 >= 1ll * n * m) {
        return -1;
    }
    for(int i = 1; i <= c; i++) {
        for(int x = xi[i] - 2; x <= xi[i] + 2; x++) {
            for(int y = yi[i] - 2; y <= yi[i] + 2; y++) {
                if(x > 0 && y > 0 && x <= n && y <= m && (x != xi[i] || y != yi[i])) {
                    np(x, y);
                }
            }
        }
    }
    if(check()) {
        return 0;
    }
    if(c + 2 == 1ll * n * m) {
        return -1;
    }
    if(m == 1 || n == 1) {
        return 1;
    }
    for(int i = 1; i <= c; i++) {
        for(int x = xi[i] - 2; x <= xi[i] + 2; x++) {
            for(int y = yi[i] - 2; y <= yi[i] + 2; y++) {
                if(!use.find(POS(x, y))) {
                    root = get(x, y);
                    if(dfn[root]) {
                        continue;
                    }
                    tarjan(root, x, y);
                }
            }
        }
    }

    for(int i = 1; i <= c; i++) {
        for(int x = xi[i] - 1; x <= xi[i] + 1; x++) {
            for(int y = yi[i] - 1; y <= yi[i] + 1; y++) {
                int s = get(x, y);
                if(cut[s]) {
                    return 1;
                }
            }
        }
    }
    return 2;
}

inline void clear() {
    mp.clear();
    use.clear();
    memset(dfn + 1, 0, tot * sizeof(int));
    memset(low + 1, 0, tot * sizeof(int));
    memset(cut + 1, 0, tot * sizeof(bool));
    memset(vis + 1, 0, tot * sizeof(int));
    memset(vis_c + 1, 0, c * sizeof(bool));
    tot = 0;
    num = 0;
    top = 0;
    return;
}

int main() {
    int T;
    read(T);
    while(T--) {
        printf("%d\n", solve());
        if(T) {
            clear();
        }
    }
    return 0;
}

后记

求点赞和评论QAQ


  目录
劳动
快乐