本题的话 BZOJ 可能数据更强一些...

Problem

https://www.luogu.org/problemnew/show/P2403

Solution

建图缩点拓扑排序...

如何建图？

每行每列建个超级点，不算这个点的权值

然后二分查找上下左右？

没啦？

复杂度稳定，就是比较卡空间。

辣鸡 BZOJ 卡我空间

Code

// Code by ajcxsu
// Problem: sotomon
 
#include<bits/stdc++.h>
using namespace std;
 
inline void gn(int &x) {
    x=0;
    char ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}
 
const int NN=1e5+10, N=2.5e6+10, R=1e6+10, M=2.5e6+10;
int h[N], hn[N], to[M], nexp[M], p=1;
int in[NN];
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }
inline void nins(int a, int b) { nexp[p]=hn[a], hn[a]=p, to[p]=b, p++; in[b]++; }
typedef pair<int, int> mpair;
vector<mpair> row[R];
int w[N], W[NN];
struct Node {
    int x,y,t;
} nod[NN];
 
int scc[N], idx, sidx;
int dfn[N], low[N];
int stk[N], t;
bool instk[N];
void tarjan(int x) {
    dfn[x]=low[x]=++idx;
    stk[++t]=x, instk[x]=1;
    for(int u=h[x];u;u=nexp[u])
        if(!dfn[to[u]]) {
            tarjan(to[u]);
            low[x]=min(low[x], low[to[u]]);
        }
        else if(instk[to[u]]) low[x]=min(low[x], dfn[to[u]]);
    if(low[x]==dfn[x]) {
        if(stk[t]==x && !w[x]) {
            t--;
            return;
        }
        ++sidx;
        do {
            scc[stk[t]]=sidx;
            instk[stk[t]]=false;
            W[sidx]+=w[stk[t]];
        } while(stk[t--]!=x);
        // printf("%d %d\n", idx, W[sidx]);
    }
}
 
int f[N];
 
int main() {
    int n,r,c;
    int x,y,t;
    gn(n), gn(r), gn(c);
    for(int i=1;i<=n;i++) {
        gn(x), gn(y), gn(t);
        row[x].push_back(mpair(y,i));
        nod[i]={x,y,t};
        ins(NN+x, i), ins(NN+R+y, i);
        w[i]=1;
    }
    for(int i=1;i<R;i++) sort(row[i].begin(), row[i].end());
    for(int i=1;i<=n;i++) {
        x=nod[i].x, y=nod[i].y, t=nod[i].t;
        if(t==1) ins(i, NN+x);
        else if(t==2) ins(i, NN+R+y);
        else {
            vector<mpair>::iterator itl,itr;
            for(int j=x-1;j<=x+1;j++) {
                itl=lower_bound(row[j].begin(), row[j].end(), mpair(y-1,0));
                itr=lower_bound(row[j].begin(), row[j].end(), mpair(y+1,0));
                while(itl!=itr) {
                    if(itl->first>=y-1 && itl->first<=y+1) ins(i, itl->second);
                    itl++;
                }
                if(itl!=row[j].end() && itl->first>=y-1 && itl->first<=y+1) ins(i, itl->second);
            }
        }
    }
    for(int i=1;i<N;i++)
        if(!dfn[i]) tarjan(i);
    for(int i=1;i<N;i++)
        for(int u=h[i];u;u=nexp[u])
            if(scc[i]!=scc[to[u]] && scc[i] && scc[to[u]]) nins(scc[i], scc[to[u]]);
    queue<int> qu;
    for(int i=1;i<=sidx;i++)
        if(!in[i]) qu.push(i), f[i]=W[i];
    int na, ans=0;
    while(!qu.empty()) {
        na=qu.front(), qu.pop();
        for(int u=hn[na];u;u=nexp[u]) {
            in[to[u]]--;
            f[to[u]]=max(f[to[u]], f[na]+W[to[u]]);
            if(!in[to[u]]) qu.push(to[u]);
        }
        ans=max(ans, f[na]);
    }
    printf("%d\n", ans);
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-p2403.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆