【BZOJ3732】Network(Kruskal重构树)
发现我还naive的不会Kruskal重构树
所谓Kruskal重构树 就是在做Kruskal的时候 构造一颗树 对两个即将合并的联通块 新建一个节点 作为这两个联通块的父亲 且这个节点的权值就是那条相连两个联通块的权值
而且这棵树很明显是一个堆
那么对于最初的最小生成树 两个节点路径上的最大/小值 就是重构树上他们的lca
然后就可以解决这道题了
#include<bits/stdc++.h>
#define N 15005
#define M 30005
using namespace std;
template<class T>
inline void read(T &x)
{
x=0;
static char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
}
int n,m,k;
struct Data
{
int from,to,val;
}e[M];
int father[2*N],val[2*N];
inline bool cmp(const Data &a,const Data &b)
{
return a.val<b.val;
}
inline int getfather(int x)
{
if(father[x]==x) return x;
father[x]=getfather(father[x]);
return father[x];
}
struct Edge
{
int to,next,val;
}edge[4*N];
int first[2*N],tot;
inline void addedge(int x,int y)
{
tot++; edge[tot].to=y; edge[tot].next=first[x]; first[x]=tot;
}
void Kruskal()
{
int sign=n;
for(int i=1;i<=2*n;i++) father[i]=i;
sort(e+1,e+m+1,cmp);
for(int i=1;i<=m;i++)
{
int fx=getfather(e[i].from),fy=getfather(e[i].to);
if(fx!=fy)
{
father[fx]=father[fy]=++sign;
val[sign]=e[i].val;
addedge(sign,fx); addedge(fx,sign);
addedge(sign,fy); addedge(fy,sign);
if(sign==2*n-1) break;
}
}
}
int depth[2*N],up[2*N][23];
void dfs(int now,int fa)
{
depth[now]=depth[fa]+1;
up[now][0]=fa;
for(int i=1;i<=20;i++) up[now][i]=up[up[now][i-1]][i-1];
for(int u=first[now];u;u=edge[u].next)
{
int vis=edge[u].to;
if(vis==fa) continue;
dfs(vis,now);
}
}
inline int lca(int x,int y)
{
if(depth[x]<depth[y]) swap(x,y);
for(int i=20;i>=0;i--) if(depth[up[x][i]]>=depth[y]) x=up[x][i];
if(x==y) return x;
for(int i=20;i>=0;i--) if(up[x][i]!=up[y][i]) x=up[x][i],y=up[y][i];
return up[x][0];
}
int main()
{
read(n); read(m); read(k);
for(int i=1;i<=m;i++) read(e[i].from),read(e[i].to),read(e[i].val);
Kruskal(); dfs(2*n-1,0);//注意是从2*n-1开始dfs
for(int i=1,x,y;i<=k;i++)
{
read(x); read(y);
cout<<val[lca(x,y)]<<'\n';
}
return 0;
}
转载于:https://www.cnblogs.com/Patrickpwq/articles/9857795.html