BZOJ 3732: Network（最小生成树+倍增）

本文主要是介绍BZOJ 3732: Network（最小生成树+倍增），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接
题意：给出一个图，每个询问的格式是：A B，表示询问从A点走到B点的所有路径中，最长的边最小值是多少

很明显最终查询的边一定是在最小生成树里面的，先跑出最小生成树，然后，可以树链剖分，也可以使用倍增来计算

#include<bits/stdc++.h>
using namespace std;#define cl(a,b) memset(a,b,sizeof(a))
#define sz(x) ((x).size())
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define ll long long
#define pb push_backconst int N = 15000+10;
const int M = N*2;
int n,m,k;
int A,B;struct Edge{int x,y,d;bool operator<(Edge a)const{return d<a.d;}
}es[M];int f[N];
void init_set(){rep(i,0,n+1)f[i]=i;}
int find_(int u){if(u==f[u])return u;return f[u]=find_(f[u]);}
void merge_(int u,int v){u=find_(u);v=find_(v);if(u==v)return;f[u]=v;}vector<pair<int,int> >G[N];int w[N][30];
int parent[N][30];
int dep[N];
void dfs(int u,int fa){rep(i,0,sz(G[u])){int v=G[u][i].first;if(v==fa)continue;w[v][0]=G[u][i].second;parent[v][0]=u;dep[v]=dep[u]+1;rep(j,1,30){int t=parent[v][j-1];if(t==0)continue;w[v][j]=max(w[v][j-1],w[t][j-1]);parent[v][j]=parent[t][j-1];}dfs(v,u);}
}
int Lca(int u,int v){int ans=0;if(dep[u]>dep[v])swap(u,v);rep(i,0,30){if((dep[v]-dep[u])>>i&1)ans=max(ans,w[v][i]),v=parent[v][i];}if(u==v)return ans;//return u;for(int i=30-1;i>=0;i--){if(parent[u][i]!=parent[v][i]){ans=max(ans,max(w[v][i],w[u][i]));u=parent[u][i];v=parent[v][i];}}return max(ans,max(w[u][0],w[v][0]));//parent[u][0];
}int main(){scanf("%d%d%d",&n,&m,&k);rep(i,0,m){scanf("%d%d%d",&es[i].x,&es[i].y,&es[i].d);}sort(es,es+m);init_set();rep(i,0,m){if(find_(es[i].x)!=find_(es[i].y)){merge_(es[i].x,es[i].y);G[es[i].x].pb(make_pair(es[i].y,es[i].d));G[es[i].y].pb(make_pair(es[i].x,es[i].d));//printf("{}  %d %d %d\n",es[i].x,es[i].y,es[i].d);}}dfs(1,1);rep(i,0,k){scanf("%d%d",&A,&B);printf("%d\n",Lca(A,B));}return 0;
}
/*
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*/