题解：P9431 [NAPC-#1] Stage3 - Jump Refreshers
DevilsFlame
·
·
题解
据题目所说，他每秒往下坠落 1 格，同时每秒 kid 可以选择：向左或向右移动 1 格，或者不移动。 意为从 i 点至 j 点需满足 |j_x - i_x| + j_y - i_y \le 0。
需注意的是：坐标系 x 轴正方向为从左到右，y 轴正方向为从下到上。
在每个跳跃球可以上升 d 个或下坠，所以建有向图，连通条件为 |j_x - i_x| + j_y - i_y \le d。
假使 u 到 v 有条路经可走，v 到 u 也油条路径，就可以缩点（如果缩点还不会就去这里：P3387 【模板】缩点）。
缩点后由有向图变为 DAG，问题也就简单了。
每个跳跃球为 1 分，包括初始跳跃球。用一数组来存储，注意 n 数组。缩点后会有重边:
（多组数据禁忌用 ```memset``` ）。
具体代码如下：
```cpp
#include<bits/stdc++.h>
#define N 3005// 养成好习惯
using namespace std;
int T,id,n,m,d,a,b,c,ans;
int dfn[N],low[N],tot,stk[N],top;
int col,to[N],s[N],mm[N];
vector <int> e[N],c_e[N];
bool in[N];
struct Node
{
int x,y;
}v[N];
inline void read(int &x)// 快读
{
x = 0;
int f = 1;
char s = getchar();
while(s < '0' || s > '9')
{
if(s == '-') f = -1;
s = getchar();
}
while(s >= '0' && s <= '9')
{
x = x * 10 + s - 48;
s = getchar();
}
x *= f;
return;
}
inline void write(int x)// 快写
{
if(x < 0)
{
putchar('-');
x *= -1;
}
if(x > 9) write(x / 10);
putchar(x % 10 + 48);
return;
}
inline void tarjan(int x)// tarjan 缩点模版
{
dfn[x] = low[x] = ++ tot;
in[x] = 1;
stk[++ top] = x;
for(int i = 0;i < e[x].size();i ++)
{
int v = e[x][i];
if(!dfn[v])
{
tarjan(v);
low[x] = min(low[x],low[v]);
}
else if(in[v]) low[x] = min(low[x],dfn[v]);
}
if(dfn[x] == low[x])// 缩点
{
col ++;
while(stk[top] != x)
{
in[stk[top]] = 0;
to[stk[top]] = col;// 染色（加入同一集合
s[col] ++;
top --;
}
s[col] ++;
to[x] = col;
in[x] = 0;
top --;
}
return;
}
inline void build()// 缩点建变
{
map <int,map <int,bool> > pl;
for(int i = 1;i <= n;i ++)
{
int u = to[i];// 代表点（染色
for(int j = 0;j < e[i].size();j ++)
{
int v = to[e[i][j]];
if(u == v || pl[u][v]) continue;
//u == v 是为了防止自环
//pl 避免重编增加时间复杂度
pl[u][v] = 1;
c_e[u].push_back(v);
}
}
return;
}
inline int dfs(int x)// 找答案
{
if(mm[x]) return mm[x];// 记忆化会吧
int r = 0;
for(int i = 0;i < c_e[x].size();i ++)
r = max(r,dfs(c_e[x][i]));
mm[x] = (r + s[x]);
return mm[x];
}
int main()
{
read(T),read(id);
while(T --)
{
tot = 0,col = 0,ans = 0;;
read(n),read(d),read(c);
for(int i = 1;i <= n;i ++)
{
read(v[i].y),read(v[i].x);// x、y 含义要注意,个人习惯x行y列
s[i] = dfn[i] = low[i] = to[i] = mm[i] = 0;// 清空，不想用memset
}
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= n;j ++)
if(i != j && abs(v[j].y - v[i].y) + v[j].x - v[i].x - d <= 0)// 建边，x、y为我个人习惯
e[i].push_back(j);
tarjan(c);
build();
write(dfs(to[c]));
putchar('\n');
for(int i = 1;i <= n;i ++) e[i].clear(),c_e[i].clear();// 勿忘清空
}
return 0;
}
```
望审核员大大通过