题解

Atcoder Beginner Contest 257 problem D 题解

本题解作者himnouth，原题目链接:https://atcoder.jp/contests/abc257/tasks/abc257_d。

题目大意

有$N$张蹦床，每张蹦床i在$(X_i,Y_i)$的位置有一个属性值$P_i$；一个人本身有一个属性值$S$。定义两蹦床之间的距离为:$dis_{i,j}=abs{X_i-X_j}+abs{Y_i-Y_j}$。
一个人在蹦床$i$能够跳到蹦床$j$,当且仅当满足: $P_i*S \geq dis_{i,j}$。

样例输入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 \geq dis_{2,3}$，因此他可以从$2$号蹦床跳到$3$号蹦床。
• 因为$P_3*S \geq 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 1e9$
• $1 \leq P_i \leq 10^9$
• 所有输入均为整型数。

解析

这道题当然可以暴力解决。
从小到大枚举$S$,对每一个$S$,枚举每一个点，看从此点能否遍历到每一个点，时间复杂度$O(玄学)$。(巨佬randnameaaa亲测，还是能过几个点的)。
不过，这种暴力解法却给我们提供了一些思路。
求S的最小值，想到优化自然能想到二分。二分$S$，若能从某一个点到达其他所有点，那么可能存在一个更优的$S$使得条件成立。若不能，则需要一个更大S的来使得条件成立。

事实上，还有一种更高明的方法，如下：

不难发现，如果把所有点看做一个图上的点，那么从一个点到达其他所有点，对应的就是这个图是一个连通图。
在使用$Floyd$算法求解最短路时，常列出递推式，如下：

$dis_{i,j}=min(dis_{i,j},dis_{i,k}+dis_{k,j});$

将其稍作变动为：

$dis_{i,j}=min(dis_{i,j},max(dis_{i,k},dis_{k,j}));$

以此递推式，可求出在路径$(i,j)$中每一次跳跃的距离最大值，再求出这些最大值的最小值即可。
此外，将$P_i \times s \geq dis_{i,j}$一式稍作变形，可得：

$S \geq \frac {dis_{i,j}} {P_i}$

由上，我们可在计算$dis_{i,j}$时，将其先除以$P_i$。因为dis_{i,j}为整数，所以需将其向上取整。

代码实现

以上算法代码实现如下：

#include<bits/stdc++.h>
using namespace std;
#define N 205
long long n,answer,dis[N][N],x[N],y[N],p[N],f[N][N];
int main(){
    std::ios::sync_with_stdio(0);
    cin>>n;
    for(long long i=1;i<=n;i++) cin>>x[i]>>y[i]>>p[i];
    for(long long i=1;i<=n;i++){
        for(long long j=1;j<=n;j++){
            long long dis=abs(x[i]-x[j])+abs(y[i]-y[j]);
            if(dis%p[i]==0) f[i][j]=dis/p[i];
            else f[i][j]=dis/p[i]+1;
        }
    }
    for(long long k=1;k<=n;k++){
        for(long long i=1;i<=n;i++){
            for(long long j=1;j<=n;j++){
                f[i][j]=min(f[i][j],max(f[i][k],f[k][j]));
            }
        }
    }
    long long ans=0xffffffff;
    for(long long i=1;i<=n;i++){
        long long res=-0x7fffffff;
        for(int j=1;j<=n;j++){
            res=max(res,f[i][j]);
        }
        ans=min(ans,res);
    }
    cout<<ans;
    return 0;
}

另附使用二分算法代码如下：

#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;
}

又附使用暴力算法代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=205;
int n;
struct node{
    int id,dis;
    bool operator<(const node w)const{
            return dis<w.dis;
    }
};
vector<node>v[N];
int x[N],y[N],p[N];
bool vis[N];
inline bool dfss(int dep,int k,int s){
    int ans=0;
    queue<int>q;
    q.push(s);
    while(1){
        if(ans==n) return 1;
        if(q.size()==0) return 0;
        int t=q.front();
        q.pop();ans++;
        int j=0;
        while(v[t][j].dis<=dep*p[t]&&j<v[t].size()){
            if(vis[v[t][j].id]) {j++;continue;}
            q.push(v[t][j].id);
            vis[v[t][j].id]=1;
            j++;
        }
    }
    return 0;
}
inline bool dfs(int dep,int k){
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof vis);
        vis[i]=1;
        if(dfss(dep,k,i)) return 1;
    }
    return 0;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>x[i]>>y[i]>>p[i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            if(i!=j)
                v[i].push_back({j,abs(x[i]-x[j])+abs(y[i]-y[j])});
        sort(v[i].begin(),v[i].end());
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<v[i].size();j++)
            cout<<v[i][j].dis<<" ";
        cout<<endl;
    }
    int depth=0;
    while(!dfs(depth,1))
        depth++;
    cout<<depth;
}

版权声明：

以上暴力算法代码及二分算法代码与题目大意皆来源于巨佬randnameaaa的题解，解析改编自巨佬randnameaaa的题解。未经过版主授权，不得随意转载。若有侵犯randnameaaa版权，请与作者联系。