Cheap Robot
题面翻译
给你一张 \(N\) 个点的带权无向连通图，其中结点 \(1,2,…,k\) 为充电中心。
一个机器人在图中行走，假设机器人的电池容量为 \(c\)，则任何时刻，机器人的电量 \(x\) 都必须满足 \(0\le x\le c\)。如果机器人沿着一条边权为 \(w\) 的边从结点 \(i\) 走到结点 \(j\)，它的电量会减少 \(w\)。机器人可以在到达某个充电中心时把电量充满。
现在有 \(q\) 个询问，每次询问机器人要从 \(a\) 点到达 \(b\) 点，电池容量至少为多少，各个询问相互独立。保证 \(a\) 点和 \(b\) 点都是充电中心。
translated by vectorwyx
题目描述
You're given a simple, undirected, connected, weighted graph with $ n $ nodes and $ m $ edges.
Nodes are numbered from $ 1 $ to $ n $ . There are exactly $ k $ centrals (recharge points), which are nodes $ 1, 2, \ldots, k $ .
We consider a robot moving into this graph, with a battery of capacity $ c $ , not fixed by the constructor yet. At any time, the battery contains an integer amount $ x $ of energy between $ 0 $ and $ c $ inclusive.
Traversing an edge of weight $ w_i $ is possible only if $ x \ge w_i $ , and costs $ w_i $ energy points ( $ x := x - w_i $ ).
Moreover, when the robot reaches a central, its battery is entirely recharged ( $ x := c $ ).
You're given $ q $ independent missions, the $ i $ -th mission requires to move the robot from central $ a_i $ to central $ b_i $ .
For each mission, you should tell the minimum capacity required to acheive it.
输入格式
The first line contains four integers $ n $ , $ m $ , $ k $ and $ q $ ( $ 2 \le k \le n \le 10^5 $ and $ 1 \le m, q \le 3 \cdot 10^5 $ ).
The $ i $ -th of the next $ m $ lines contains three integers $ u_i $ , $ v_i $ and $ w_i $ ( $ 1 \le u_i, v_i \le n $ , $ u_i \neq v_i $ , $ 1 \le w_i \le 10^9 $ ), that mean that there's an edge between nodes $ u $ and $ v $ , with a weight $ w_i $ .
It is guaranteed that the given graph is simple (there is no self-loop, and there is at most one edge between every pair of nodes) and connected.
The $ i $ -th of the next $ q $ lines contains two integers $ a_i $ and $ b_i $ ( $ 1 \le a_i, b_i \le k $ , $ a_i \neq b_i $ ).
输出格式
You have to output $ q $ lines, where the $ i $ -th line contains a single integer : the minimum capacity required to acheive the $ i $ -th mission.
样例 #1
样例输入 #1
10 9 3 1
10 9 11
9 2 37
2 4 4
4 1 8
1 5 2
5 7 3
7 3 2
3 8 4
8 6 13
2 3
样例输出 #1
12
样例 #2
样例输入 #2
9 11 3 2
1 3 99
1 4 5
4 5 3
5 6 3
6 4 11
6 7 21
7 2 6
7 8 4
8 9 3
9 2 57
9 3 2
3 1
2 3
样例输出 #2
38
15
提示
In the first example, the graph is the chain $ 10 - 9 - 2^C - 4 - 1^C - 5 - 7 - 3^C - 8 - 6 $ , where centrals are nodes $ 1 $ , $ 2 $ and $ 3 $ .
For the mission $ (2, 3) $ , there is only one simple path possible. Here is a simulation of this mission when the capacity is $ 12 $ .
- The robot begins on the node $ 2 $ , with $ c = 12 $ energy points.
- The robot uses an edge of weight $ 4 $ .
- The robot reaches the node $ 4 $ , with $ 12 - 4 = 8 $ energy points.
- The robot uses an edge of weight $ 8 $ .
- The robot reaches the node $ 1 $ with $ 8 - 8 = 0 $ energy points.
- The robot is on a central, so its battery is recharged. He has now $ c = 12 $ energy points.
- The robot uses an edge of weight $ 2 $ .
- The robot is on the node $ 5 $ , with $ 12 - 2 = 10 $ energy points.
- The robot uses an edge of weight $ 3 $ .
- The robot is on the node $ 7 $ , with $ 10 - 3 = 7 $ energy points.
- The robot uses an edge of weight $ 2 $ .
- The robot is on the node $ 3 $ , with $ 7 - 2 = 5 $ energy points.
- The robot is on a central, so its battery is recharged. He has now $ c = 12 $ energy points.
- End of the simulation.
Note that if value of $ c $ was lower than $ 12 $ , we would have less than $ 8 $ energy points on node $ 4 $ , and we would be unable to use the edge $ 4 \leftrightarrow 1 $ of weight $ 8 $ . Hence $ 12 $ is the minimum capacity required to acheive the mission.
—
The graph of the second example is described here (centrals are red nodes):
The robot can acheive the mission $ (3, 1) $ with a battery of capacity $ c = 38 $ , using the path $ 3 \rightarrow 9 \rightarrow 8 \rightarrow 7 \rightarrow 2 \rightarrow 7 \rightarrow 6 \rightarrow 5 \rightarrow 4 \rightarrow 1 $
The robot can acheive the mission $ (2, 3) $ with a battery of capacity $ c = 15 $ , using the path $ 2 \rightarrow 7 \rightarrow 8 \rightarrow 9 \rightarrow 3 $
先用 dijkstra 求出每个点距离离他最近的关键点的距离，设点 \(u\) 的距离为 \(d_u\)
设点 \(u\) 的容量为 \(x_u\)，那么 一定满足 \(c-d_u\ge x_u\ge d_u\)，因为他一定要能从最近的关键点走来，再走回最近的关键点。
那么点 \(u\) 到 \(v\) 有一条边权为 \(w\) 的边的话， \(d_v\le x_u-w\le c-d_u-w\)
可以得到 \(c\ge d_u+d_v+w\)，现在要找一个最大边权最小的路径，发现这个就是最小生成树上的路径。
多次询问就倍增。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+5;
int n,m,k,q,e_num,hd[N],id[N<<2],v[N],fa[N],f[N][20],dep[N];
LL d[N],mx[N][20];
struct edge{
int u,v,nxt;
LL w;
}e[N<<3];
int find(int x)
{
if(fa[x]==x)
return x;
return fa[x]=find(fa[x]);
}
void add_edge(int u,int v,LL w)
{
e[++e_num]=(edge){u,v,hd[u],w};
hd[u]=e_num;
}
struct node{
int v;
LL w;
bool operator<(const node&n)const{
return w>n.w;
}
};
void dijkstra()
{
priority_queue<node>q;
memset(d,0x7f,sizeof(d));
for(int i=1;i<=k;i++)
q.push((node){i,d[i]=0});
while(!q.empty())
{
int k=q.top().v;
q.pop();
if(v[k])
continue;
v[k]=1;
for(int i=hd[k];i;i=e[i].nxt)
{
if(d[e[i].v]>d[k]+e[i].w)
{
d[e[i].v]=d[k]+e[i].w;
q.push((node){e[i].v,d[e[i].v]});
}
}
}
}
int cmp(int x,int y)
{
return e[x].w<e[y].w;
}
void kruskal()
{
static int u[N<<2],v[N<<2];
static LL w[N<<2];
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++)
e[id[i]].w+=d[e[id[i]].u]+d[e[id[i]].v];
sort(id+1,id+m+1,cmp);
for(int i=1;i<=m;i++)
u[i]=e[id[i]].u,v[i]=e[id[i]].v,w[i]=e[id[i]].w;
memset(hd,0,sizeof(hd));
e_num=0;
for(int i=1;i<=m;i++)
{
if(find(u[i])^find(v[i]))
{
fa[find(u[i])]=find(v[i]);
add_edge(u[i],v[i],w[i]),add_edge(v[i],u[i],w[i]);
}
}
}
void dfs(int x,int y)
{
f[x][0]=y,dep[x]=dep[y]+1;
for(int i=1;i<20;i++)
f[x][i]=f[f[x][i-1]][i-1],mx[x][i]=max(mx[x][i-1],mx[f[x][i-1]][i-1]);
for(int i=hd[x];i;i=e[i].nxt)
if(e[i].v^y)
mx[e[i].v][0]=e[i].w,dfs(e[i].v,x);
}
LL ask(int x,int y)
{
LL ans=0;
if(dep[x]<dep[y])
swap(x,y);
for(int i=19;~i;i--)
if(dep[f[x][i]]>=dep[y])
ans=max(ans,mx[x][i]),x=f[x][i];
if(x==y)
return ans;
for(int i=19;~i;i--)
if(f[x][i]^f[y][i])
ans=max({ans,mx[x][i],mx[y][i]}),x=f[x][i],y=f[y][i];
return max({ans,mx[x][0],mx[y][0]});
}
int main()
{
scanf("%d%d%d%d",&n,&m,&k,&q);
for(int i=1,u,v,w;i<=m;i++)
scanf("%d%d%d",&u,&v,&w),add_edge(u,v,w),id[i]=e_num,add_edge(v,u,w);
dijkstra();
kruskal();
dfs(1,0);
while(q--)
{
int u,v;
scanf("%d%d",&u,&v);
printf("%lld\n",ask(u,v));
}
}