BZOJ 1924 [SDOI 2010] 所驼门王的宝藏 (优化建图+tarjan+最长链)

题意

题解

如果能把图建出来就是求一个缩点后的最长链。

这个建图是可以优化的。

考虑同一行的横天门，我们随便找一个横天门$u$。然后用这个点$u$向这一行所有的有效点连单向边。然后再用这一行的其他横天门朝$u$连单向边。可以发现与原图等价。

丛寰门同理。

自由门直接连。

然后就完事了。

CODE

#pragma GCC optimize ("O2")
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXM = 1000005;
const int dx[] = { 1, 1, 1, -1, -1, -1, 0, 0 };
const int dy[] = { -1, 0, 1, 1, 0, -1, 1, -1 };
int n, r, c, x[MAXN], y[MAXN], op[MAXN];
vector<int>R[MAXM], C[MAXM];
map< pair<int,int>,int >id;
int fir[MAXN], to[MAXM], nxt[MAXM], cnt;
inline void link(int u, int v) {
    if(u == v) return;
    to[++cnt] = v, nxt[cnt] = fir[u], fir[u] = cnt;
}
inline void build() {
    for(int i = 1; i <= r; ++i) {
        int k = -1;
        for(int j = R[i].size()-1; j >= 0; --j) if(op[R[i][j]] == 1) {k = R[i][j];break;}
        if(~k) {
            for(int j = R[i].size()-1; j >= 0; --j) {
                link(k, R[i][j]);
                if(op[R[i][j]] == 1) link(R[i][j], k);
            }
        }
    }
    for(int i = 1; i <= c; ++i) {
        int k = -1;
        for(int j = C[i].size()-1; j >= 0; --j) if(op[C[i][j]] == 2) {k = C[i][j];break;}
        if(~k) {
            for(int j = C[i].size()-1; j >= 0; --j) {
                link(k, C[i][j]); 
                if(op[C[i][j]] == 2) link(C[i][j], k);
            }
        }
    }
    for(int i = 1; i <= n; ++i)
        if(op[i] == 3) {
            for(int j = 0; j < 8; ++j) {
                int u = x[i] + dx[j];
                int v = y[i] + dy[j];
                if(id[make_pair(u,v)]) link(i, id[make_pair(u,v)]);
            }
        }
}
int dfn[MAXN], low[MAXN], tmr, stk[MAXN], scc[MAXN], indx, scccnt, sz[MAXN];
void tarjan(int u) {
    dfn[u] = low[u] = ++tmr;
    stk[++indx] = u;
    for(int i = fir[u], v; i; i = nxt[i])
        if(!dfn[v=to[i]]) tarjan(v), low[u] = min(low[u], low[v]);
        else if(!scc[v]) low[u] = min(low[u], dfn[v]);
    if(low[u] == dfn[u]) {
        ++scccnt;
        do {
            scc[stk[indx]] = scccnt;
            ++sz[scccnt];
        }while(stk[indx--] != u); 
    }
}
int in[MAXN], f[MAXN], q[MAXN], s, t;
vector<int>G[MAXN];
int main () {
    scanf("%d%d%d", &n, &r, &c);
    for(int i = 1; i <= n; ++i) {
        scanf("%d%d%d", &x[i], &y[i], &op[i]);
        R[x[i]].push_back(i);
        C[y[i]].push_back(i);
        id[make_pair(x[i],y[i])] = i;
    }
    build();
    for(int i = 1; i <= n; ++i)
        if(!dfn[i]) tarjan(i);
    for(int i = 1; i <= n; ++i)
        for(int j = fir[i]; j; j = nxt[j])
            if(scc[i] != scc[to[j]])
                G[scc[i]].push_back(scc[to[j]]), ++in[scc[to[j]]];
    for(int i = 1; i <= scccnt; ++i) if(!in[i]) q[t++] = i;
    int ans = 0;
    while(s < t) {
        int u = q[s++];
        ans = max(ans, (f[u]+=sz[u]));
        for(int i = G[u].size()-1, v; i >= 0; --i) {
            if((--in[v=G[u][i]]) == 0) q[t++] = v;
            f[v] = max(f[v], f[u]);
        }
    }
    printf("%d
", ans);
}