题解 Atcoder

Atcoder Beginner Contest 257 problem D 题解

---

题目链接:点我

题目大意

有N张蹦床，每张蹦床i在$(x_i,y_i)$的位置有一个属性值$p_i$;一个人本身有一个属性值$S$。定义两蹦床之间的距离为:

$$dis_{i,j}=|x_i-x_j|+|y_i-y_j|$$
一个人在$i$蹦床能够跳到$j$蹦床,当且仅当满足:
$$p_i*S\geq dis_{i,j}$$
求一个最小的$S$,使得一个人从某一蹦床出发，能够到达所有蹦床。

---

样例输入1

4
-10 0 1
0 0 5
10 0 1
11 0 1

样例输出1

2

样例解释1

当$S=1$时，不存在一张蹦床，使得从此开始可以跳到所有蹦床。
当$S=2$时，他可以从$2$号蹦床开始，跳到所有蹦床。
例如，他跳到$4$号蹦床可以用如下操作:

• 因为$p_2*S>=dis_{2,3}$，因此他可以从$2$号蹦床跳到$3$号蹦床。
• 因为$p_3*S>=dis_{3,4}$，因此他可以从$3$号蹦床跳到$4$号蹦床。

样例输入2

7
20 31 1
13 4 3
-10 -15 2
34 26 5
-2 39 4
0 -50 1
5 -20 2

样例输出2

18

数据范围

• $2\leq N\leq 200$
• $-10^9\leq x_i,y_i\leq 10^9$
• $1\leq p_i\leq 10^9$
• $(x_i,y_i)\neq(x_j,y_j)(i\neq j)$
• 所有输入均为整型数。

---

解析

这道题当然可以暴力解决。
从小到大枚举$S$,对每一个$S$,枚举每一个点，看从此点能否遍历到每一个点，时间复杂度$O(玄学)$。(亲测，还是能过几个点的(doge))

不过，这种暴力解法却给我们提供了一些思路。

• 求$S$的最小值，想到优化自然能想到二分。二分$S$，若能从某一个点到达其他所有点，那么可能存在一个更优的$S$使得条件成立。若不能，则需要一个更大的$S$来使得条件成立。

那么如何去快速判断能否从某一个点到达其他所有点呢？

• 不难发现，如果把所有点看做一个图上的点，那么从一个点到达其他所有点，对应的就是这个图是一个连通图。

于是问题得到简化。对于每两个点$i,j$，如果从$i$能够到达$j$，则这个图上从$i$到$j$有一条边。

用邻接矩阵存储这个图，最后直接用Floyd算法即可直接判断是否连通。

需要注意的是，能够从$i$走到$j$，并不意味着能够从$j$走到$i$，也就是说，这个图不是双向的。不能算出一向，就定了另一向。还有就是要注意数据范围，亲测不开$long\ long$会$WA$。

---

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=205;
#define int long long //超级懒狗
int n;
int x[N],y[N],p[N];
int a[N][N]; //a[i][j]表示从i到j的距离
bool b[N][N]; //邻接矩阵
inline bool check(int mid){
    memset(b,0,sizeof b); //多次check,需要初始化
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j)
                b[i][j]=(p[i]*mid>=a[i][j]); //若i能到j，则b[i][j]=1;否则为0。
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(i!=j&&j!=k&&i!=k)
                    b[i][j]|=b[i][k]&b[k][j]; //Floyd模板
    for(int i=1;i<=n;i++){
        bool g=1;
        for(int j=1;j<=n;j++)
            if(b[i][j]==0&&i!=j) g=0;
        if(g) return 1;
    } //枚举每个点，看从此点能否到达其他所有点，即是否b[i]中除第i个数以外的元素都为1
    return 0;
}
signed main() //signed超懒型
{
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%lld%lld%lld",&x[i],&y[i],&p[i]); 
        for(int j=1;j<i;j++)
            a[i][j]=a[j][i]=abs(x[i]-x[j])+abs(y[i]-y[j]); //计算距离
    }
    int l=0,r=1e10,ans=0;
    while(l<=r){
        int mid=(l+r)/2;//long long间不能使用位运算
        if(check(mid)) r=mid-1,ans=mid;
        else l=mid+1;
    } //二分模板(注意l与r的取值)
    cout<<ans; 
    return 0;
}

完结撒花~