题解 CF1253F 【Cheap Robot】
ez_lcw
2021-01-25 09:35:34
首先发现所有询问点都是充电桩这个条件很有用。
它能滋生出一种暴力到极端的想法：用 Floyd 对全局跑一遍最短路。然后新建一个图，图中两两充电桩连一条边，边权为它们之间的最短路，代表着从这个充电桩直接走到那个充电桩最少要备多少电。然后再把新图的最小生成树建出来，询问时直接询问树上两点路径边权最大值。
发现时间压根过不去，也不太好直接优化。
发现瓶颈主要是在跑 Floyd $O(n^3)$ 和建图 $O(k^2)$，这是我们我们远远不能接受的。
但是原图最多也就 $m$ 条边，所以上面的做法只能把时间复杂化。
于是考虑能不能直接在题目给的原图上搞东西。
于是就有了一种神奇的思路：
既然充电桩直接两两建边我们不能接受，我们不如直接枚举 $c$，把两个距离 $\leq c$ 的充电桩之间连一条边，然后再看题目询问的 $A$ 和 $B$ 充电桩在什么时候联通。
但是枚举 $c$ 貌似也要跟充电桩两两间的距离有关，那怎么转移到原图上的边呢？
在原图上，我们先用 dijkstra 预处理出每一个点 $i$ 到离它最近的充电桩的距离 $dis_i$。然后设当前枚举的为 $c$：
然后对于原图中的每一条边 $(u,v)$，设其边权为 $w$。如果 $dis_u+w+dis_v\leq c$，，那么就连上边 $(u,v)$，然后再判断 $A$ 和 $B$ 在原图中是否联通。
为什么这样做是对的呢？（以下的 $A$ 和 $B$ 均代表任意两个充电桩）
1. 若 $(u,v)$ 被连上，那么 $u$ 和 $v$ 的最近充电桩间的距离 $\leq c$。
证明显然，根据 $(u,v)$ 被连上的条件的定义即可得出。
2. 若 $A$ 和 $B$ 的距离 $\leq c$，那么 $A$、$B$ 联通。
如果两个充电桩 $A$ 和 $B$ 的距离 $\leq c$，那么这样做之后他们一定联通。因为对于 $A$ 和 $B$ 最短路上的每一条边 $(u,v)$，它肯定能满足 $dis_u+w+dis_v\leq c$，因为这个式子代表着从离 $u$ 最近的充电桩出发、能经过 $(u,v)$ 走到离 $v$ 最近的充电桩且满足路程 $\leq c$，而从 $A$ 走到 $B$ 肯定算入一种方案，所以 $(u,v)$ 这条边肯定能连上。
3. 推广到间接联通上，如果 $A$ 和 $B$ 联通，$A$ 就真的能到达 $B$ 吗？
答案是肯定的，因为 $A$ 和 $B$ 的联通路径上的每一条边都被连上，那么根据上述两点证明，可以得出这条边的两个端点的最近充电桩可以互相到达，而 $A$ 可以通过这些能互相到达的充电桩直接或间接地到达 $B$。
所以这样做是正确的。
至于维护连边的过程，我们可以用并查集。
同时我们可以把询问离线下来，在并查集的每个联通块内记录这个连通块内包含的未解决询问，而合并连通块时要用启发式合并才能保证时间复杂度，具体详见代码。
然后枚举 $c$ 实在是太大了，不然直接先把每条边按 $dis_u+w+dis_v$ 排序，再依次枚举边。
这样你就发现这种 “给边排序，再依次加入图中判断联通” 的方法和 kruskal 类似，只不过边权改了一下而已，而且还带上了询问。
具体代码如下：
```cpp
#include<bits/stdc++.h>
#define N 100010
#define M 300010
#define ll long long
using namespace std;
struct Edge
{
int u,v;
ll w;
}e[M];
struct Query
{
int a,b;
ll ans;
Query(){ans=-1;}
}q[M];
struct data
{
int u;
ll s;
data(){};
data(int a,ll b){u=a,s=b;}
bool operator < (const data &a) const
{
return s>a.s;
}
};
int n,m,k,Q;
int fa[N];
int cnt,head[N],nxt[M<<1],to[M<<1],w[M<<1];
ll dis[N];
vector<int>g[N];
priority_queue<data>que;
void adde(int u,int v,int wi)
{
to[++cnt]=v;
w[cnt]=wi;
nxt[cnt]=head[u];
head[u]=cnt;
}
void dijkstra()
{
memset(dis,127,sizeof(dis));
for(int i=1;i<=k;i++)
que.push(data(i,0)),dis[i]=0;
while(!que.empty())
{
data now=que.top();
que.pop();
for(int i=head[now.u];i;i=nxt[i])
{
int v=to[i];
if(dis[now.u]+w[i]<=dis[v])
{
dis[v]=dis[now.u]+w[i];
que.push(data(v,dis[v]));
}
}
}
}
bool cmp(Edge a,Edge b)
{
return a.w<b.w;
}
int find(int x)
{
return x==fa[x]?x:(fa[x]=find(fa[x]));
}
int main()
{
scanf("%d%d%d%d",&n,&m,&k,&Q);
for(int i=1;i<=m;i++)
{
scanf("%d%d%lld",&e[i].u,&e[i].v,&e[i].w);
adde(e[i].u,e[i].v,e[i].w),adde(e[i].v,e[i].u,e[i].w);
}
for(int i=1;i<=Q;i++)
{
scanf("%d%d",&q[i].a,&q[i].b);
g[q[i].a].push_back(i),g[q[i].b].push_back(i);
}
dijkstra();
for(int i=1;i<=m;i++)
e[i].w=e[i].w+dis[e[i].u]+dis[e[i].v];
sort(e+1,e+m+1,cmp);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
{
int a=find(e[i].u),b=find(e[i].v);
if(a!=b)
{
if(g[b].size()<g[a].size()) swap(a,b);//注意启发式合并的size比较不是比较的并查集的size而是询问大小的size
fa[a]=b;
for(int j=0,size=g[a].size();j<size;j++)
{
int x=find(q[g[a][j]].a),y=find(q[g[a][j]].b);
if(x==y)
{
if(q[g[a][j]].ans==-1)
q[g[a][j]].ans=e[i].w;
}
else g[b].push_back(g[a][j]);
}
}
}
for(int i=1;i<=Q;i++)
printf("%lld\n",q[i].ans);
return 0;
}
```