题解：P9431 [NAPC-#1] Stage3 - Jump Refreshers

· · 题解

题意

在一个平面中有 n 个互不重叠的点，开始时你在点 c 上。当你在点上时可以向上跳 d 格，当你不在点上时每秒会下降 1 格，同时可以向左或右移动一格，也可以不移动。问你最多可以到达多少个不同的点（相同的点可以重复经过）。

思路

不难想到，我们可以按点之间能否到达将题目给出的点连边，然后得到一张有向图，图上每个点的点权为 1。对于最终答案的路径，他是会有很多路径被重复经过的，这样会导致暴力的复杂度很高，于是我们可以对其进行缩点，因为缩点后图是没有环的，所以缩点后搜索的复杂度会降低很多，然后再搭配上最优性剪枝就可以通过此题。

代码

#include<bits/stdc++.h>
using namespace std;
vector<int>a[3001];
int idx=0,dfn[3001],low[3001],Color=0;
bool bj[3001];
int n,m,color[3001];
int ww[3001];
stack<int>q;
int d,c;
void read(int &x){//快读
    char ch=getchar();
    int f=1;
    x=0;
    while(ch<'0'||ch>'9'){
        if(ch=='-'){
            f=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-48;
        ch=getchar();
    }
    x*=f;
}
void dfs(int p){//tarjan内的搜索
    bj[p]=1;
    dfn[p]=low[p]=++idx;
    q.push(p);
    for(auto it:a[p]){
        if(!dfn[it]){
            dfs(it);
            low[p]=min(low[p],low[it]);
        }
        else{
            if(bj[it]){
                low[p]=min(low[p],dfn[it]);
            }
        }
    }
    if(dfn[p]==low[p]){
        Color++;
        while(q.top()!=p){
            bj[q.top()]=0;
            color[q.top()]=Color;
            q.pop();
            ww[Color]++;
        }
        bj[p]=0;
        q.pop();
        color[p]=Color;
        ww[Color]++;//缩点后的点权会改变，ww数组表示的是缩点后的点权
    }
}
void tarjan(){//tarjan缩点
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            dfs(i);
        }
    }
}
vector<int>t[3001];
int ans[3001];
bool vis[3001];
void Dfs(int p,int www){
    vis[p]=1;
    ans[p]=max(ans[p],www);
    for(auto it:t[p]){
        if(!vis[it]&&www+ww[it]>ans[it]){//最优性剪枝
            Dfs(it,www+ww[it]);
        }
    }
    vis[p]=0;
}
int x[3001],y[3001];
int main(){
    int T,id;
    read(T);
    read(id);
    while(T){
        T--;
        idx=0;//多测清空
        for(int i=1;i<=n;i++){
            dfn[i]=0;
            low[i]=0;
            a[i].clear();
        }
        for(int i=1;i<=Color;i++){
            ans[i]=0;
            t[i].clear();
            ww[i]=0;
        }
        Color=0;
        read(n);
        read(d);
        read(c);
        while(!q.empty()){
            q.pop();
        }
        for(int i=1;i<=n;i++){
            read(x[i]);
            read(y[i]);
        }
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(y[i]-y[j]+d-abs(x[i]-x[j])>=0){//连边
                    a[i].push_back(j);
                }
                if(y[j]-y[i]+d-abs(x[i]-x[j])>=0){
                    a[j].push_back(i);
                }
            }
        }
        tarjan();
        for(int i=1;i<=Color;i++){//缩点
            for(int j=1;j<=n;j++){
                if(color[j]==i){
                    for(auto it:a[j]){
                        if(color[it]==i){
                            continue;
                        }
                        t[i].push_back(color[it]);
                    }
                }
            }
        }
        Dfs(color[c],ww[color[c]]);//跑一遍dfs求答案
        int wwww=0; 
        for(int i=1;i<=Color;i++){//枚举最大答案
            wwww=max(wwww,ans[i]);
        }
        printf("%d\n",wwww);//输出
    }
    return 0;
}

AC 记录。