BZOJ 3732 Network 【模板】kruskal重构树

【题解】

首先，我们可以发现，A到B的所有路径中，最长边的最小值一定在最小生成树上。我们用Kruskal最小生成树时，假设有两个点集U，V，若加入一条边w(u,v)使U，V联通，那么w就是U中每个点到V中每个点的路径上的最长边。因为我们每次在可选的w中选择了最小的，所以可以满足最长边最短的要求。

我们可以做kruskal，当A与B恰好连通时，当前加入的边w就是A中的每个点到B中的每个点的最长边。

但这种做法在本题中似乎不可行。。因为本题中询问有很多组，效率上有问题（或者是我太傻了QAQ

其实也可以先跑kruskal，再做LCA倍增法来求a到b的最长边

我的做法是kruskal重构树，方法是按照kruskal求最小生成树的方式加边，但每次在加边时，新建一个节点，然后把两个点集的代表元作为其左右儿子，把新建节点的点权设为当前边的边权。

然后我们可以发现这棵树具有一些神奇的性质：

1.这棵树是一棵二叉树；

2.这棵树的父亲的点权大于左右儿子的点权；

3.在原图上，任意两点之间的路径的最长边的最小值等于kruskal重构树上它们的Lca的点权。

这样，这道题就可以完美解决了。

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=100010;

int n,m,k,tot,x,y,fa[maxn],f[maxn][32],val[maxn],dep[maxn];

struct edge{int x,y,w;}e[maxn];

struct child{int l,r;}ch[maxn];

void read(int &k){

	k=0; int f=1; char c=getchar();

	while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();

	while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar();

	k*=f;

}

int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

bool cmp(edge a,edge b){return a.w<b.w;}

void dfs(int u){if (ch[u].l) dep[ch[u].l]=dep[ch[u].r]=dep[u]+1,dfs(ch[u].l),dfs(ch[u].r);}

int lca(int x,int y){

	if (dep[x]<dep[y]) swap(x,y);

	for (int i=0,t=dep[x]-dep[y];i<20;i++) if (t&(1<<i)) x=f[x][i];

	for (int i=19;i>=0;i--) if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];

	return f[x][0];

}

int main(){

	read(n); read(m); read(k); tot=n;

	for (int i=1;i<=m;i++) read(e[i].x),read(e[i].y),read(e[i].w);

	sort(e+1,e+1+m,cmp);

	for (int i=1;i<=n;i++) fa[i]=i,fa[i+n]=i+n;

	for (int i=1;i<=m;i++) if (find(x=e[i].x)!=find(y=e[i].y)){

		ch[++tot].l=find(x); ch[tot].r=find(y);

		fa[find(x)]=fa[find(y)]=f[find(x)][0]=f[find(y)][0]=tot;

		val[tot]=e[i].w;

	}

	dfs(tot);

	for (int j=1;j<20;j++) for (int i=1;i<=tot;i++) f[i][j]=f[f[i][j-1]][j-1];

	for (int i=1;i<=k;i++) read(x),read(y),printf("%d\n",val[lca(x,y)]);

	return 0;

}