luogu题解 CF1253F Cheap Robot

Description

\(n\) 个点，\(m\) 条边，\(k\) 个充电站，\(Q\) 次询问，每次询问给出两个点 \(p_1\) , \(p_2\) ，两个点一定在充电站上，问从 \(p_1\) 到 \(p_2\) 的电池容量最少需要多少

题目传送

前置知识

• 最短路算法
• 最小生成树算法
• 倍增求LCA / 树链剖分

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
#include
#include
#include
#include
//#include
#define LL long long
#define int long long
#define orz cout<<"lkp AK IOI!"< 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 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<= 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<