自动搬运

查看原文

来自洛谷，原作者为

	ycy1124 ENTJ-A | 有事私。| 清关了，私信基本也不会回关（除非满足条件），但可以支持小号回关 | 出去玩去了。不在线。微信可能上。

搬运于2025-08-24 22:48:19，当前版本为作者最后更新于2024-09-30 10:02:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

在一个平面中有 $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 记录。