Cheap Robot

题目翻译：

给一个带$N$个点的带权无向连通图，并给定$k$每经过一个边就要消耗边的边权$w$，而当到达$1 \sim k$的节点处可以将点充满。求从$a$到$b$所需要的最小点容量$c$。及一次性消耗的电量不能超过$c$。

前置知识：

$1.$最近公共祖先$LCA$

$2.$最小生成树$kruskal$

$3.$并查集

$4.$最短路$dijkstra$

思路：

普通解法：

我们读完题肯定可以想到，用全源最短路求$1 \sim k$的最短路，再求每个节点所邻的最近的充电节点，求出里面耗电的最大值最小即可，但这样复杂度就到了$n^2logn$，肯定会超

正解：

1.我们在仔细思考会发现，我们要尽量把机器人移到充电站，在在充电站之间移动一般是最优的，因此我们可以预处理出每个节点离充电站的最小距离$dis_i$。那如何求了。我们可以先建一个超级原点$0$号点，它与所有充电站，即$1 \sim k$有一条边权为零的边，则由这个点到任意节点的最短路就是这个节点到最近充电站的距离。原因是，任意非充电站节点到超级原点必经过充电站，而充电站到超级原点的边权为零，则该点到超级原点的最短路等于到充电站的最短路。因此只需跑一遍$dijkstra$求出$dis_i$即可。

建边

for(int i=1;i<=m;i++){
	int u,v,w;
	cin>>u>>v>>w;
	e[u].push_back({v,w});
	e[v].push_back({u,w});
}
for(int i=1;i<=k;i++){
	e[0].push_back({i,0});
}

$dijkstra$

int dis[N],vis[N];
vector<edge>e[N];
priority_queue<node>q;
void dijkstra(){
	memset(dis,0x3f,sizeof(dis));
	dis[0]=0;
	q.push({0,0});
	while(!q.empty()){
		int u=q.top().u;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(auto ed:e[u]){
			int v=ed.v,w=ed.w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push({v,dis[v]});
			}
		}
	}
}

2.又由已知条件，$c$，当前剩余电量$k$，和点离充电站的最短路$dis_i$可得出关系
$$$c \geq x \geq dis_i$$$
而从充电站走到点至少消耗了$dis_i$则不等式可以改为
$$$c-dis_i \geq x \geq dis_i$$$
令下一个点为$j$边权为$w_{i,j}$,同理有
$$$c-dis_j \geq x-w_{i,j} \geq dis_j$$$
将两个式子合并即可得到
$$$dis_j \le c-dis_i-w_{i,j}$$$
简单转换可知
$c \geq dis_i+dis_j+w_{i,j}$
则由此可知从$i$到$j$的最小消耗电量为$dis_i+dis_j+w_{i,j}$。

3.既然已经求出两点之间的最小消耗电量，而题目又是多次询问，求最大电容量及从$a$到$b$的每条路的最大耗电量的最小值，因此我们可以先将任意两点之间的边权换成$dis_i+dis_j+w_{i,j}$，在跑一遍$kruskal$求出最小生成树。在求任意两点路径上边权的最大值即可

建新图

for(int u=1;u<=n;u++){
	for(auto ed:e[u]){
		now.push_back({u,ed.v,ed.w+dis[u]+dis[ed.v]});
	}
}

$kruskal$

int fa[N];
int find(int x){
	if(fa[x]==x)return x;
	else return fa[x]=find(fa[x]);
}
void kruskal(){
	sort(now.begin(),now.end(),cmp);
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	int cnt=0;
	for(auto ed:now){
		if(find(ed.u)!=find(ed.v)){
			cnt++;
			tr[ed.u].push_back({ed.v,ed.w});
			tr[ed.v].push_back({ed.u,ed.w});
			fa[find(ed.u)]=find(ed.v);
			if(cnt==n-1)break;
		}
	}
}

4.要求树上的路径问题，我们可以简单想到求$LCA$，于是直接用倍增求$LCA$，只需要将求和改为求$max$即可

$LCA$

int f[N][22];
int deep[N],maxm[N][22];
void init(){
	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]);
        }
	}
}
void dfs(int p,int father){
    f[p][0]=father;
	for(auto ed:tr[p]){
		int v=ed.v,w=ed.w;
        if(v==father)continue;
		maxm[v][0]=w;
		deep[v]=deep[p]+1;
		dfs(v,p);
	}
}
int lca(int x,int y){
	int ans=0;
	if(deep[x]<deep[y])swap(x,y);
	for(int i=20;i>=0;i--){
		if(deep[f[x][i]]<deep[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]));
		x=f[x][i];
		y=f[y][i];
	}
	ans=max(ans,max(maxm[x][0],maxm[y][0]));
	return ans;
}

完整流程：

$1.$建图，并将所有$1 \sim k$的点连向超级原点，边权为零
$2.$跑一遍以超级原点为起点的$dijkstra$，求出$dis_i$
$3.$将任意两点间边的边权改为$dis_i+dis_j+w_{i,j}$，建立新图
$4.$跑一遍新图$kruskal$求出最小生成树
$5.$在最小生成树上求$LCA$，维护路径中边权的最大值，并输出结果

完整代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
struct edge{
	int v,w;
}; 
struct node{
	int u,dis;
	bool operator<(const node &a)const{return dis>a.dis;}
};
struct E{
	int u,v,w;
};
bool cmp(E x,E y){
	return x.w<y.w;
}
vector<E>now;
vector<edge>tr[N];
int n,m;
int dis[N],vis[N];
vector<edge>e[N];
priority_queue<node>q;
void dijkstra(){
	memset(dis,0x3f,sizeof(dis));
	dis[0]=0;
	q.push({0,0});
	while(!q.empty()){
		int u=q.top().u;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(auto ed:e[u]){
			int v=ed.v,w=ed.w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push({v,dis[v]});
			}
		}
	}
}
int fa[N];
int find(int x){
	if(fa[x]==x)return x;
	else return fa[x]=find(fa[x]);
}
int f[N][22];
int deep[N],maxm[N][22];
void init(){
	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]);
        }
	}
}
void dfs(int p,int father){
    f[p][0]=father;
	for(auto ed:tr[p]){
		int v=ed.v,w=ed.w;
        if(v==father)continue;
		maxm[v][0]=w;
		deep[v]=deep[p]+1;
		dfs(v,p);
	}
}
int lca(int x,int y){
	int ans=0;
	if(deep[x]<deep[y])swap(x,y);
	for(int i=20;i>=0;i--){
		if(deep[f[x][i]]<deep[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]));
		x=f[x][i];
		y=f[y][i];
	}
	ans=max(ans,max(maxm[x][0],maxm[y][0]));
	return ans;
}
void kruskal(){
	sort(now.begin(),now.end(),cmp);
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	int cnt=0;
	for(auto ed:now){
		if(find(ed.u)!=find(ed.v)){
			cnt++;
			tr[ed.u].push_back({ed.v,ed.w});
			tr[ed.v].push_back({ed.u,ed.w});
			fa[find(ed.u)]=find(ed.v);
			if(cnt==n-1)break;
		}
	}
}
signed main(){
	int k,q;
	cin>>n>>m>>k>>q;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		e[u].push_back({v,w});
		e[v].push_back({u,w});
	}
	for(int i=1;i<=k;i++){
		e[0].push_back({i,0});
	}
	dijkstra();
	for(int u=1;u<=n;u++){
		for(auto ed:e[u]){
			now.push_back({u,ed.v,ed.w+dis[u]+dis[ed.v]});
		}
	}
	kruskal();
	deep[1]=1;
	dfs(1,-1);
    init();
	
	while(q--){
		int x,y;
		cin>>x>>y;
		cout<<lca(x,y)<<endl;
	}
}