BZOJ 3732 Network

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=30009;int n,m,T;struct Edge{int u,v,d;}edges[maxn];bool cmp(const Edge &rhs1,const Edge &rhs2){return rhs1.d<rhs2.d;}int father[maxn];int Getf(int x){if(father[x]==x)return x;return father[x]=Getf(father[x]);}void Unionn(int x,int y){int fx=Getf(x);int fy=Getf(y);if(fx!=fy)father[fx]=fy;}int cntedge;int head[maxn];int to[maxn<<1],nex[maxn<<1],dist[maxn];void Addedge(int x,int y,int z){nex[++cntedge]=head[x];to[cntedge]=y;dist[cntedge]=z;head[x]=cntedge;}int f[maxn][20],g[maxn][20],dep[maxn];void Dfs(int now,int fa){dep[now]=dep[fa]+1;for(int i=head[now];i;i=nex[i]){if(to[i]==fa)continue;f[to[i]][0]=now;g[to[i]][0]=dist[i];Dfs(to[i],now);}}void LCAinit(){for(int j=1;j<=19;++j){for(int i=1;i<=n;++i){f[i][j]=f[f[i][j-1]][j-1];g[i][j]=max(g[i][j-1],g[f[i][j-1]][j-1]);}}}int GetMaxd(int u,int v){int ret=0;if(dep[u]<dep[v])swap(u,v);for(int j=19;j>=0;--j){if(dep[f[u][j]]>=dep[v]){ret=max(ret,g[u][j]);u=f[u][j];}}if(u==v)return ret;for(int j=19;j>=0;--j){if(f[u][j]!=f[v][j]){ret=max(ret,max(g[u][j],g[v][j]));u=f[u][j];v=f[v][j];}}return max(ret,max(g[u][0],g[v][0]));}int main(){scanf("%d%d%d",&n,&m,&T);for(int i=1;i<=m;++i)scanf("%d%d%d",&edges[i].u,&edges[i].v,&edges[i].d);sort(edges+1,edges+1+m,cmp);for(int i=1;i<=n;++i)father[i]=i;for(int i=1;i<=m;++i){int u=edges[i].u;int v=edges[i].v;int d=edges[i].d;if(Getf(u)==Getf(v))continue;Unionn(u,v);Addedge(u,v,d);Addedge(v,u,d);}Dfs(1,0);LCAinit();////for(int i=1;i<=n;++i){//printf("%d %d\n",f[i][0],g[i][0]);//}while(T--){int x,y;scanf("%d%d",&x,&y);printf("%d\n",GetMaxd(x,y));}return 0;}