题解 UVA11354 【Bond】

# 思路 最小生成树+倍增LCA ### 题意其实就是要求询问中两个点之间最短路径的最大边。 ### 因为给的是边权 所以生成树考虑用Kruscal并同时建树，用结构体存边和建的树的点，然后bfs倍增存最大边，最后lca即可。 注意这道UVA的题有一个坑点：多组数据，因此每次数据输入前要清零，而且每组数据输出之间要空一行！！ #### 下面贴代码 有注释。 ------------ ``` #include<bits/stdc++.h> using namespace std; const int N=5e5+5; int head[N],cnt,n,m,q,st[N][24],gw[N][24],fa[N],dep[N],t; //st存父节点，gw存最大权值,fa并查集祖先，dep深度 struct dy{ //e存边 其中u，v端点，w权值；edge存点，u为序号，v为连的边，w为权值 int u,v,w; }edge[N],e[N]; int find(int u){return fa[u]=fa[u]==u?u:find(fa[u]);} //并查集 void Add(int x,int y,int z){ //链式前向* edge[++cnt].u=head[x]; edge[cnt].v=y; edge[cnt].w=z; head[x]=cnt; } bool cmp(dy a,dy b){ //kruscal需要用到的排序 return a.w<b.w; } void kruscal(){ 建最小生产树保存节点 int mst=0; sort(e+1,e+m+1,cmp); for(int i=1;i<=n;i++) fa[i]=i;//并查集初始化 for(int i=1;i<=m;i++){ int vx=find(e[i].u),vy=find(e[i].v); if(vx==vy)continue; Add(e[i].u,e[i].v,e[i].w);//无向图连2遍 Add(e[i].v,e[i].u,e[i].w); fa[vx]=vy; if(++mst==n-1)break; //如果连了n-1条边则完成 } } void dfs(int u,int fa,int dis){ dep[u]=dep[fa]+1; gw[u][0]=dis,st[u][0]=fa; for(int i=1;(1<<i)<=dep[u];i++){ //倍增不多说 st[u][i]=st[st[u][i-1]][i-1]; gw[u][i]=max(gw[u][i-1],gw[st[u][i-1]][i-1]); } for(int i=head[u];i;i=edge[i].u)//遍历连接的节点 if(edge[i].v!=fa) dfs(edge[i].v,u,edge[i].w); } int lca(int u,int v){ //lca直接返回最大值 int res=-2e8; if(dep[u]<dep[v])swap(u,v);//把u看做深点 for(int i=21;i>=0;i--) if(dep[st[u][i]]>=dep[v]){//u跳 并更新 res=max(res,gw[u][i]); u=st[u][i]; } if(u==v) return res; for(int i=21;i>=0;i--){//u v一起跳 更新 if(st[u][i]==st[v][i])continue; res=max(res,gw[u][i]); res=max(res,gw[v][i]); u=st[u][i],v=st[v][i]; } return max(max(gw[u][0],res),gw[v][0]);//因为最后一次父节点相同时退出循环 所以把更新加上 } int main(){ while(scanf("%d%d",&n,&m)!=EOF){ //读到输出末尾结束 if(t++>0)printf("\n"); //第二组及以后先输出回车 cnt=0; memset(head,0,sizeof(head)); memset(st,0,sizeof(st)); memset(gw,0,sizeof(gw)); memset(fa,0,sizeof(fa)); memset(dep,0,sizeof(dep)); memset(e,0,sizeof(e)); memset(edge,0,sizeof(edge)); for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); kruscal(); for(int i=1;i<=n;i++) if(!dep[i]) dfs(i,0,0); scanf("%d",&q); for(int sta,end,i=1;i<=q;i++){ scanf("%d%d",&sta,&end); if(find(sta)!=find(end))printf("-1\n");//如果不在同一个连通图上就不行 else printf("%d\n",lca(sta,end)); } } return 0; } ``` ```