题解 CF1253F 【Cheap Robot】

· · 题解

Description

题目传送

前置知识

Solution

考虑如何求出任意一个点到离它最近的充电站的距离？

暴力的做法是对每一个充电站跑一边单源最短路，但复杂度实在承受不了

有一个很巧妙的处理方法是，我们可以建一个超级源点，连向所有充电站，权值设为 0，然后在新图上跑一个最短路，就能求出所有点到离它最近的充电站得距离了

有什么用？别急，让我们接着往下看

设走到一个点 i，剩余电量为 x， 那么一定有 x > dis_i （不管是中途充电还是到达终点均成立，因为保证了终点也是充电站）

假设我们要求的电容量为 c，那么三者关系满足：

c \ge x \ge dis_i

因为走到 i 点至少消耗了 dis_i 的电（最少的情况是以对 i 来说它的起点刚好是最近的充电站来说的），那么上面的不等式可以改为：

c - dis_i \ge x \ge dis_i

设下一个点为 j，边权为 w_{i,j}，同理有：

c - dis_j \ge x - w_{i,j} \ge dis_j

结合上面两个式子，进行合并得到 dis_j \le x - w_{i,j}，即：

dis_j \le c - dis_i - w_{i,j}

交换一下位置：

c \ge dis_i + dis_j + w_{i,j}

这个不等式的含义为，从 i 点到 j 点所需最小的电池容量为 dis_i + dis_j + w_{i,j}，也就是说没条边的最小限制已经求出来了，用这个最小限制就可以更新图上所有的边

那么每次询问一个起点 a 到 b 的最小电池容量，就是找一条从 a 点到 b 点的路径，使得这个路径上的最大值最小

很像二分？ 但用不着那么麻烦

因为这条路径一定在最小生成树上，同时在这个最小生成树上每对点都有一个简单路径，最小生成树的构建过程也保证了这条简单路径上的最大值就是答案

那么用LCA+倍增法求出路径上的最大值即可（也可以用树链剖分来实现，前提是码力足够强）

具体实现来看代码

Code

/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)

思路极其鬼畜：
1、最短路
2、生成树
3、倍增+LCA
4、查询 
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
//#include<time.h>
#define LL long long
#define int long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 4e5+5;
const int MAXM = 6e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;

struct edge{
    int from, to, w, nxt;
}e[MAXM << 2], E[MAXM], E2[MAXM << 1];
int head[MAXN], num_edge = 0;
int Head[MAXN], Num_edge = 0;

struct node{
    int bh, val;
    bool operator < (const node &b) const { return val > b.val; }
};

int n, m, k, Q, cnt;
int dis[MAXN], fa[MAXN], f[MAXN][22], dep[MAXN], maxm[MAXN][22];
bool vis[MAXN];
priority_queue<node> q;

int read(){
    int s = 0, f = 0;
    char ch = getchar();
    while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
    while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
    return f ? -s : s;
}

bool cmp(edge x, edge y){ return x.w < y.w; }
void add_edge(int from, int to, int w){ e[++num_edge] = (edge){from, to, w, head[from]}, head[from] = num_edge; }
void Add_edge(int from, int to, int w){ E2[++Num_edge] = (edge){from, to, w, Head[from]}, Head[from] = Num_edge; }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

void dij(){//跑一边dij求出所有点到最近的充电站的距离
    memset(dis, 0x3f, sizeof dis);
    dis[0] = 0;
    q.push((node){0, 0});
    while(!q.empty()){
        node u = q.top(); q.pop();
        if(vis[u.bh]) continue;
        vis[u.bh] = true;
        for(int i = head[u.bh]; i; i = e[i].nxt){
            int v = e[i].to;
            if(dis[v] > dis[u.bh] + e[i].w){
                dis[v] = dis[u.bh] + e[i].w;
                if(!vis[v]) q.push((node){v, dis[v]});
            }
        }
    }
}

void kruskal(){//建出更新权值后的图的最小生成树
    for(int i = 1; i <= n; ++i) fa[i] = i;//重置父亲 
    for(int i = 1; i <= m; ++i){
//      cout<<E[i].from<<" "<<E[i].to<<" "<<E[i].w<<"lkp"<<endl;
        int uf = find(E[i].from), vf = find(E[i].to);
        if(uf != vf){
//          orz;
//          if(rand() % 2) fa[uf] = vf;//随机连父亲，随机化优化复杂度 
//          else 
            fa[vf] = uf;
            Add_edge(E[i].from, E[i].to, E[i].w), Add_edge(E[i].to, E[i].from, E[i].w);//建出最小生成树来 
            cnt++;
            if(cnt == n - 1) return ;//如果建了n - 1条边，就结束 
        }
    }
}

void dfs(int u, int fa){//dfs预处理lca ，注意这里跑的是新图
    f[u][0] = fa;
    for(int i = Head[u]; i; i = E2[i].nxt){
        int v = E2[i].to;
        if(v == fa) continue;
        dep[v] = dep[u] + 1;
        maxm[v][0] = E2[i].w;
//      cout<<maxm[v][0]<<endl;
        dfs(v, u);
    }
}

void init(){//倍增法预处理lca，顺便维护一个最大值
    for(int i = 1; i <= 20; ++i){
        for(int j = 1; j <= n; ++j){
            f[j][i] = f[f[j][i - 1]][i - 1];
            maxm[j][i] = max(maxm[j][i - 1], maxm[f[j][i - 1]][i - 1]);
//          cout<<maxm[j][i]<<endl;
        }
    }
}

int get_max(int x, int y){//可以直接在求两点lca的过程中求出两点简单路径的最大值
    int ans = 0;
    if(dep[x] < dep[y]) swap(x, y);
    for(int i = 20; i >= 0; --i){
        if(dep[f[x][i]] < dep[y]) continue;
        ans = max(ans, maxm[x][i]);
        x = f[x][i];
    }
    if(x == y) return ans;
    for(int i = 20; i >= 0; --i){
        if(f[x][i] == f[y][i]) continue;
        ans = max(ans, max(maxm[x][i], maxm[y][i]));
//      cout<<ans<<endl;
        x = f[x][i];
        y = f[y][i];
    }
    ans = max(ans, max(maxm[x][0], maxm[y][0]));
    return ans;
}

signed main()
{
//  srand(time(0));
    n = read(), m = read(), k = read(), Q = read();
    for(int i = 1, u, v, w; i <= m; ++i){
        u = read(), v = read(), w = read();
        add_edge(u, v, w), add_edge(v, u, w);
        E[i].from = u, E[i].to = v, E[i].w = w;
    }
    for(int i = 1; i <= k; ++i){
        add_edge(0, i, 0), add_edge(i, 0, 0);    
    }
    dij();
//  for(int i = 1; i <= n; ++i) cout<<i<<" "<<dis[i]<<" lkp"<<endl;
    for(int i = 1; i <= m; ++i){//更新边的权值
        E[i].w += dis[E[i].from] + dis[E[i].to];
    }
    sort(E + 1, E + m + 1, cmp);//按边权大小由小到大排序 
    kruskal();

//  memset(minn, 0x7f, sizeof minn);
    dep[1] = 1;
    dfs(1, -1);
    init();

    for(int i = 1, u, v; i <= Q; ++i){
        u = read(), v = read();
        cout<<get_max(u, v)<<endl;//直接输出所求结果即可
    }
    return 0;
}