洛谷P9235 [蓝桥杯 2023 省 A] 网络稳定性

$\text{[Problem Discription]}$

给定一个 $n$ 个点和 $m$ 条无向边组成的图，每条边都有一个边权 ${\omega }_i$。

一条路径的稳定性定义为这条路径上所有边的边权的最小值。

从给定节点 $u$ 到 $v$ 的总价值定义为从 $u$ 到 $v$ 的所有路径各自稳定性的最大值。如果没有路径联通 $u,v$，那么价值为 $-1$。

$q$ 组询问，每次询问给定 $u,v$，求 $u$ 到 $v$ 的总价值。

$1\le n,q\le 1\times 10^5,1\le m\le 3\times 10^5$。

$\text{[Analysis]}$

最小值最大的问题一般都是二分，但是这题不是。

首先是否联通可以用并查集求解，非常简单。

可以先考虑图联通的情况，不联通的情况不过也就是由几个联通的图组成。

考虑一个 $n$ 个点 $m$ 条边的联通的图（注意这里的 $n,m$ 和题目里的 $n,m$ 意义不相同）。首先先证明最终答案一定是最大生成树里的边。

证明依旧是采用反证法：如果最终答案里某一条路径不是最大生成树里的路径，那么我们考虑那条不在最大生成树里的边：

1. 它的边权小于最大生成树里的最小边，那么既然最大生成树就足以把图里的所有节点联通，并且稳定性更好，为什么非要走这条边呢？
2. 它的边权大于最大生成树里的最小边，它不在最大生成树肯定是因为最大生成树里有那么一条路径，这条路径上所有边的稳定性比这条边要大，而且这条路径联通了这条路径的两个节点（假设这两个节点是 $u,v$）。既然这样，我们的路径就可以这么修正：其它边不变，这条不在最大生成树里的边用最大生成树里联通 $u,v$ 的若干条边代替。这样总答案一定不会变劣。

既然答案一定诞生在最大生成树里，那就先把最大生成树建立出来呀。

建立最大生成树后，由于在树上任意两个节点间一定有且只有一条路径连接。问题就变成了求这条路径上所有边的稳定性的最小值。

树上倍增的典例呀。类似于倍增求 LCA 的那种算法。在求 LCA 的同时顺带可以把这个值求出。

具体来说，就是设 $f_{i,u}$ 表示从 $u$ 到其 $2^i$ 级祖先的路径的最小值，那么有：

$$f_{i,u}=\min \left\{f_{i-1,u},f_{i-1,{\text{fa}}_{i-1,u}}\right\}$$

其中 ${\text{fa}}_{i,u}$ 表示 $u$ 的第 $2^i$ 级祖先。

总时间复杂度 $O(n\log n)$。

$\text{Code}$

const int N=1e5+100;
const int M=3e5+100;
const int inf=0x3f3f3f3f;struct PraticalLink{int u,v,w;bool operator < (PraticalLink t) const{return w>t.w;}
}Link[M];struct UnionFind{int Fa[N],n;void clear(int n){for(int i=1;i<=n;i++) Fa[i]=i; }int getf(int x){if (Fa[x]==x) return x;return Fa[x]=getf(Fa[x]);}void merge(int x,int y){int u=getf(x),v=getf(y);if (u==v) return;Fa[v]=u;}bool query(int u,int v){return getf(u)==getf(v);}
}Reach,Kru;//封装一个并查集struct edge{int nxt,to,val;
}e[M<<1];int h[N],ecnt;
inline void add(int u,int v,int w){e[++ecnt]=(edge){h[u],v,w};h[u]=ecnt;e[++ecnt]=(edge){h[v],u,w};h[v]=ecnt;
}int n,m,q;void Kruskal(){sort(Link+1,Link+m+1);Kru.clear(n);for(int i=1;i<=m;i++)if (!Kru.query(Link[i].u,Link[i].v)){add(Link[i].u,Link[i].v,Link[i].w);Kru.merge(Link[i].u,Link[i].v);}//建立最小生成树
}int Fa[22][N],minn[22][N],dep[N];void dfs(int u,int fa){dep[u]=dep[fa]+1;for(int i=h[u];i;i=e[i].nxt){int v=e[i].to;if (v==fa) continue;Fa[0][v]=u;minn[0][v]=e[i].val;dfs(v,u);}
}
void dispose(){for(int j=1;j<=20;j++)for(int i=1;i<=n;i++){Fa[j][i]=Fa[j-1][Fa[j-1][i]];minn[j][i]=min(minn[j-1][i],minn[j-1][Fa[j-1][i]]);}
}//树上倍增
int query(int u,int v){int ans=inf;if (dep[u]<dep[v]) swap(u,v);for(int i=20;i>=0;i--)if (dep[u]-dep[v]>=(1<<i)){ckmin(ans,minn[i][u]);u=Fa[i][u];}if (u==v) return ans;for(int i=20;i>=0;i--)if (Fa[i][u]!=Fa[i][v]){ckmin(ans,min(minn[i][u],minn[i][v]));u=Fa[i][u];v=Fa[i][v];}ckmin(ans,min(minn[0][u],minn[0][v]));return ans;
}int main(){n=read();m=read();q=read();Reach.clear(n);for(int i=1;i<=m;i++){Link[i].u=read();Link[i].v=read();Link[i].w=read();Reach.merge(Link[i].u,Link[i].v);}Kruskal();for(int i=1;i<=n;i++)if (Reach.Fa[i]==i) dfs(i,0);dispose();for(int i=1;i<=q;i++){int u=read(),v=read();if (!Reach.query(u,v)) printf("-1\n");else printf("%d\n",query(u,v));}return 0;
}read() 表示快读
ckmin(a,b) 表示取 a,b 间的较小值并把之赋值给 a