[ABC257D] Jumping Takahashi 2 Solution

更好的阅读体验戳此进入

题面

给定 $n$$n$ 个不共点的蹦床，第 $i$$i$ 个蹦床的位置为 $(x_i,y_i)$$(x_i, y_i)$，反弹力为 $p_i$$p_i$。存在整数 $S$$S$。定义能从第 $i$$i$ 个蹦床跳到第 $j$$j$ 个蹦床当且仅当 $p_i\times S\ge |x_i-x_j|+|y_i-y_j|$$p_i \times S \ge \lvert x_i - x_j \rvert + \lvert y_i - y_j \rvert$。你需要钦定一个起点，使得可以从该蹦床抵达所有蹦床（可以多步），并最小化 $S$$S$，输出最小值。

Solution

不难发现问题可以转化为，我们要选择一个点，求使得这个点能够到达其它所有点的最大代价，然后求所有起点最大代价的最小值，这东西有点像全源最短路，且数据范围很小。于是不难想到一步转化，可以将原不等式转化为 $S\ge {\displaystyle \frac{|x_i-x_j|+|y_i-y_j|}{p_i}}$$S \ge \dfrac{\lvert x_i - x_j \rvert + \lvert y_i - y_j \rvert}{p_i}$，显然 $S$$S$ 存在单调性，所以自然可以令 $S=\lceil {\displaystyle \frac{|x_i-x_j|+|y_i-y_j|}{p_i}}\rceil$$S = \left\lceil \dfrac{\lvert x_i - x_j \rvert + \lvert y_i - y_j \rvert}{p_i} \right\rceil$。于是可以认为 $i\to j$$i \rightarrow j$ 的边权即为这个，然后跑一遍 FLoyd，维护每个源点的最大值，最后取个最小值即可，复杂度 $O(n^3)$$O(n^3)$。当然不用 Floyd，或者改用 bfs + 二分答案，都是可以做到 $O(n^2\log n)$$O(n^2 \log n)$ 的，不过意义不大。

Code

xxxxxxxxxx
66
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
int N;
26
struct Node{ll x, y, p;}nod[300];
27
ll dis[300][300];
28
ll ans(LONG_LONG_MAX);
29

30
int main(){
31
    N = read();
32
    for(int i = 1; i <= N; ++i)nod[i].x = read(), nod[i].y = read(), nod[i].p = read();
33
    for(int i = 1; i <= N; ++i)
34
        for(int j = 1; j <= N; ++j)
35
            if(i == j)dis[i][j] = 0;
36
            else
37
                dis[i][j] = (ll)ceil((ld)(abs(nod[i].x - nod[j].x) + abs(nod[i].y - nod[j].y)) / (ld)nod[i].p),
38
                dis[j][i] = (ll)ceil((ld)(abs(nod[i].x - nod[j].x) + abs(nod[i].y - nod[j].y)) / (ld)nod[j].p);
39
    for(int k = 1; k <= N; ++k)
40
        for(int i = 1; i <= N; ++i)
41
            for(int j = 1; j <= N; ++j)
42
                dis[i][j] = min(dis[i][j], max(dis[i][k], dis[k][j]));
43
    for(int s = 1; s <= N; ++s){
44
        ll mx(-1);
45
        for(int t = 1; t <= N; ++t)mx = max(mx, dis[s][t]);
46
        ans = min(ans, mx);
47
    }printf("%lld\n", ans);
48
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
49
    return 0;
50
}
51

52
template < typename T >
53
inline T read(void){
54
    T ret(0);
55
    int flag(1);
56
    char c = getchar();
57
    while(c != '-' && !isdigit(c))c = getchar();
58
    if(c == '-')flag = -1, c = getchar();
59
    while(isdigit(c)){
60
        ret *= 10;
61
        ret += int(c - '0');
62
        c = getchar();
63
    }
64
    ret *= flag;
65
    return ret;
66
}

UPD

update-2022_12_09 初稿