题目描述
给你N个点的无向图 (1 <= N <= 15,000)，记为：1…N。
图中有M条边 (1 <= M <= 30,000) ，第j条边的长度为： d_j ( 1 < = d_j < = 1,000,000,000).
现在有 K个询问 (1 < = K < = 20,000)。
每个询问的格式是：A B，表示询问从A点走到B点的所有路径中，最长的边最小值是多少？
输入
第一行： N, M, K。
第2..M+1行: 三个正整数：X, Y, and D (1 <= X <=N; 1 <= Y <= N). 表示X与Y之间有一条长度为D的边。
第M+2..M+K+1行: 每行两个整数A B,表示询问从A点走到B点的所有路径中，最长的边最小值是多少？
输出
对每个询问，输出最长的边最小值是多少。
样例输入
6 6 8
1 2 5
2 3 4
3 4 3
1 4 8
2 5 7
4 6 2
1 2
1 3
1 4
2 3
2 4
5 1
6 2
6 1
样例输出
5
5
5
4
4
7
4
5
题解
kruskal重构树。在kruskal的时候，如果两个点不在一个集合里，那么新建一个结点作为他们祖先的父亲，并将这条边的边权赋为新建结点的点权。这样，原问题就变为在这棵kruskal重构树上求x，y两点lca的点权。
// kruskal重构树 #include<cmath>#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>using namespace std;#define ll long longconst int maxn=200000+50;int n,m,k,aa,bb,fat[maxn],cnt;int fir[maxn],to[maxn],nex[maxn],ecnt;int son[maxn],dep[maxn],sz[maxn],fa[maxn],top[maxn],val[maxn];struct node{int x,y,z;}a[maxn];void add_edge(int u,int v){ ???nex[++ecnt]=fir[u];fir[u]=ecnt;to[ecnt]=v;}int cmp(const node &a,const node &b){ ???return a.z<b.z;}int father(int x){ ???if(x!=fat[x]) fat[x]=father(fat[x]); ???return fat[x];}void dfs1(int x,int f,int deep){ ???dep[x]=deep; ???fa[x]=f; ???sz[x]=1; ???int maxson=-1; ???for(int e=fir[x];e;e=nex[e]){ ???????int v=to[e]; ???????if(v==f) continue; ???????dfs1(v,x,deep+1); ???????sz[x]+=sz[v]; ???????if(sz[v]>maxson) maxson=sz[v],son[x]=v; ???}}void dfs2(int x,int topf){ ???top[x]=topf; ???if(!son[x]) return ; ???dfs2(son[x],topf); ???for(int e=fir[x];e;e=nex[e]){ ???????int v=to[e]; ???????if(v==fa[x]||v==son[x]) continue; ???????dfs2(v,v); ???}}template<typename T>void read(T& aa){ ???char cc; ll ff;aa=0;cc=getchar();ff=1; ???while((cc<‘0‘||cc>‘9‘)&&cc!=‘-‘) cc=getchar(); ???if(cc==‘-‘) ff=-1,cc=getchar(); ???while(cc>=‘0‘&&cc<=‘9‘) aa=aa*10+cc-‘0‘,cc=getchar(); ???aa*=ff;}void kruskal(){ ???sort(a+1,a+1+m,cmp); ???for(int i=1;i<=m;i++){ ???????if(father(a[i].x)!=father(a[i].y)){ ???????????int fa=father(a[i].x),fb=father(a[i].y); ???????????val[++cnt]=a[i].z; ???????????fat[cnt]=fat[fa]=fat[fb]=cnt; ???????????add_edge(fa,cnt); ???????????add_edge(cnt,fa); ???????????add_edge(fb,cnt); ???????????add_edge(cnt,fb); ???????} ???}}int lca(int x,int y){ ???int f1=top[x],f2=top[y]; ???while(f1!=f2){ ???????if(dep[f1]<dep[f2]) swap(f1,f2),swap(x,y); ???????x=fa[f1];f1=top[x]; ???} ???return dep[x]<dep[y]?x:y;}int main(){ ???read(n),read(m),read(k);cnt=n; ???for(int i=1;i<=m;i++) ???read(a[i].x),read(a[i].y),read(a[i].z); ???for(int i=1;i<=n;i++) fat[i]=i; ???kruskal(); ???dfs1(cnt,0,1);dfs2(cnt,cnt); ???while(k--){ ???????read(aa),read(bb); ???????cout<<val[lca(aa,bb)]<<endl; ???} ???return 0;}【bzoj3732】Network
原文地址：https://www.cnblogs.com/rlddd/p/9594268.html