【题解】BZOJ 1924 [SDOI2010]所驼门王的宝藏

Problem

在一个 $R\times C$ 的矩形空间中,有 $n$ 个有 宝藏和传送门 的特殊点,能且仅能通过传送门进行移动
有三种传送门:

  1. 横向传送
  2. 纵向传送
  3. 八连通传送

传送门只能传送到另外一个有传送门的点

求从任何一个点开始最多能够拿到多少宝藏

Thought

比较简单的一个题

横纵优化连边,八连通用 unordered_map 暴力查询, $Tarjan$ 缩点,在 $DAG$ 上 $DP$ 即可

Code

#include <bits/stdc++.h>
using namespace std;

int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}

const int N = 100010;

int X[N], Y[N];
int difx, dify;

struct Door {
    int x, y, type;
}dr[N];

int n;

vector <int> xx[N];
vector <int> yy[N];

unordered_map <int, int> mp[N];
unordered_map <int, bool> hs[N];

int xxx[N];
int yyy[N];

struct Graph {
    int f[N * 10], t[N * 10], n[N * 10];
    int head[N], tot;
    void add(int u, int v) {
        if(u == v) return;
        ++ tot;
        f[tot] = u; t[tot] = v;
        n[tot] = head[u]; head[u] = tot;
    }
}G, H;

int dfn[N], low[N], DFN;
int id[N], siz[N], cnt;

int sta[N], top;
bool vis[N];

int deg[N];
int Ans[N];
void dfs(int x) {
    dfn[x] = low[x] = ++ DFN;
    sta[++ top] = x; vis[x] = 1;
    for(int i = G.head[x]; i; i = G.n[i]) {
        int t = G.t[i];
        if(!dfn[t]) {
            dfs(t);
            low[x] = min(low[x], low[t]);
        }
        else if(vis[t])
            low[x] = min(low[x], dfn[t]);
    }
    if(dfn[x] == low[x]) {
        ++ cnt;
        while(sta[top] != x) {
            id[sta[top]] = cnt;
            vis[sta[top]] = 0;
            sta[top --] = 0;
            ++ siz[cnt];
        }
        id[sta[top]] = cnt;
        vis[sta[top]] = 0;
        sta[top --] = 0;
        ++ siz[cnt];
    }
}

int DFS(int x) {
    if(Ans[x]) return Ans[x];
    for(int i = H.head[x]; i; i = H.n[i])
        Ans[x] = max(Ans[x], DFS(H.t[i]));
    Ans[x] += siz[x];
    return Ans[x];
}

int main() {
    n = read(); read(); read();
    for(int i = 1; i <= n; ++ i) {
        X[i] = dr[i].x = read();
        Y[i] = dr[i].y = read();
        dr[i].type = read();
        mp[dr[i].x][dr[i].y] = i;
    }
    sort(X + 1, X + n + 1);
    sort(Y + 1, Y + n + 1);
    difx = unique(X + 1, X + n + 1) - X - 1;
    dify = unique(Y + 1, Y + n + 1) - Y - 1;
    for(int i = 1; i <= n; ++ i) {
        if(dr[i].type == 3) {
            if(mp[dr[i].x - 1][dr[i].y - 1])
                G.add(i, mp[dr[i].x - 1][dr[i].y - 1]);

            if(mp[dr[i].x - 1][dr[i].y])
                G.add(i, mp[dr[i].x - 1][dr[i].y]);

            if(mp[dr[i].x - 1][dr[i].y + 1])
                G.add(i, mp[dr[i].x - 1][dr[i].y + 1]);

            if(mp[dr[i].x][dr[i].y - 1])
                G.add(i, mp[dr[i].x][dr[i].y - 1]);

            if(mp[dr[i].x][dr[i].y + 1])
                G.add(i, mp[dr[i].x][dr[i].y + 1]);

            if(mp[dr[i].x + 1][dr[i].y - 1])
                G.add(i, mp[dr[i].x + 1][dr[i].y - 1]);

            if(mp[dr[i].x + 1][dr[i].y])
                G.add(i, mp[dr[i].x + 1][dr[i].y]);

            if(mp[dr[i].x + 1][dr[i].y + 1])
                G.add(i, mp[dr[i].x + 1][dr[i].y + 1]);
        }
        dr[i].x = lower_bound(X + 1, X + difx + 1, dr[i].x) - X;
        dr[i].y = lower_bound(Y + 1, Y + dify + 1, dr[i].y) - Y;
        xx[dr[i].x].push_back(i);
        yy[dr[i].y].push_back(i);
        if(dr[i].type == 1 && !xxx[dr[i].x])
            xxx[dr[i].x] = i;
        if(dr[i].type == 2 && !yyy[dr[i].y])
            yyy[dr[i].y] = i;
    }
    for(int i = 1; i <= difx; ++ i) {
        if(!xxx[i]) continue;
        for(auto it : xx[i]) {
            G.add(xxx[i], it);
            if(dr[it].type == 1)
                G.add(it, xxx[i]);
        }
    }
    for(int i = 1; i <= dify; ++ i) {
        if(!yyy[i]) continue;
        for(auto it : yy[i]) {
            G.add(yyy[i], it);
            if(dr[it].type == 2)
                G.add(it, yyy[i]);
        }
    }
    for(int i = 1; i <= n; ++ i)
        if(!dfn[i])
            dfs(i);
    for(int i = 1; i <= G.tot; ++ i)
        if(id[G.f[i]] != id[G.t[i]] && !hs[id[G.f[i]]].count(id[G.t[i]])) {
            ++ deg[id[G.t[i]]];
            H.add(id[G.f[i]], id[G.t[i]]);
            hs[id[G.f[i]]][id[G.t[i]]] = 1;
        }

    int ans = 0;
    for(int i = 1; i <= cnt; ++ i)
        if(!deg[i])
            ans = max(ans, DFS(i));
    printf("%d\n", ans);
    return 0;
}
Comments

添加新评论