BZOJ 3732 Network Kruskal重构树
题目大意:给定一个n个点m条边的无向连通图,k次询问两点之间所有路径中最长边的最小值
Kruskal+倍增LCA做法见http://blog.csdn.net/popoqqq/article/details/39755703
LCT做法见http://blog.csdn.net/popoqqq/article/details/39929277
Kruskal重构树真是强大……一不小心手滑就RANK1啥的……
每加入一条边时,我们并不链接这条边的两端点,而是把这条边两端点所在并查集的根连接起来,而且是按秩合并
这样做的好处就是任何一个节点到根的路径长度不超过logn
且由于Kruskal重构树的性质,两点之间的最长边和原图相同,且最长边的一端连接的一定是两点的LCA
于是直接暴力向上找就行 如果加上倍增的话或许能优化到O(loglogn)
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 15100 using namespace std; struct abcd{ int x,y,f; bool operator < (const abcd &Y) const { return f < Y.f ; } }edges[M<<1]; int n,m,k; int belong[M],fa[M],size[M],dis[M],dpt[M]; int Find(int x) { if(!belong[x]) belong[x]=x,size[x]=1; if(belong[x]==x) return x; return belong[x]=Find(belong[x]); } int Get_Depth(int x) { if(dpt[x]) return dpt[x]; if(!fa[x]) return dpt[x]=1; return dpt[x]=Get_Depth(fa[x])+1; } void Kruskal() { int i; sort(edges+1,edges+m+1); for(i=1;i<=m;i++) { int x=Find(edges[i].x); int y=Find(edges[i].y); if(x==y) continue ; if(size[x]>size[y]) swap(x,y); belong[x]=y; size[y]=max(size[y],size[x]+1); fa[x]=y; dis[x]=edges[i].f; } } int Query(int x,int y) { int re=0; if(dpt[x]<dpt[y]) swap(x,y); while(dpt[x]>dpt[y]) re=max(re,dis[x]),x=fa[x]; while(x!=y) re=max(re,dis[x]),re=max(re,dis[y]),x=fa[x],y=fa[y]; return re; } int main() { int i,x,y; cin>>n>>m>>k; for(i=1;i<=m;i++) scanf("%d%d%d",&edges[i].x,&edges[i].y,&edges[i].f); Kruskal(); for(i=1;i<=n;i++) Get_Depth(i); for(i=1;i<=k;i++) { scanf("%d%d",&x,&y); printf("%d\n", Query(x,y) ); } }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。