题目链接
思路:
有时候树上的问题用LCA比最短路那些算法要高效的多.
题目中要求从A到比路径的最大值,那么这个值肯定在图中所有短构成的一个最大生成树上(首先一个连通图可以满足任意两点互相到达,其次又满足路径尽可能的大).所以对于这个题我们先要求最大生成树.
其次,k比较大,如果用朴素的LCA求的话每次O(n),实践不允许,所以我们就需要用倍增法LCA去求,预处理OO(nlogn)，查询依次logn.适用于查询次数多的时候.
倍增法求LCA
#include<bits/stdc++.h> #define Ri(a) scanf("%d", &a) #define Rl(a) scanf("%lld", &a) #define Rf(a) scanf("%lf", &a) #define Rs(a) scanf("%s", a) #define Pi(a) printf("%d\n", (a)) #define Pf(a) printf("%lf\n", (a)) #define Pl(a) printf("%lld\n", (a)) #define Ps(a) printf("%s\n", (a)) #define W(a) while(a--) #define CLR(a, b) memset(a, (b), sizeof(a)) #define MOD 100000007 #define inf 0x3f3f3f3f #define exp 0.00000001 #define pii pair<int, int> #define mp make_pair #define pb push_back using namespace std; typedef long long ll; const int maxn=1e5+10; const int maxm=5e4+10; struct node { int u,v,w; }q[2*maxn]; int pre[maxm],dis[maxm][100],depth[maxm],parent[100][maxm];//parent表示每次往上走2^k步的父亲,dis表示每次走2^k路径的最小值 int m,n,qq,kk; vector<pii>vt[maxm]; int ans=inf; int cmp(node a,node b) { return a.w>b.w; } void init() { for(int i=1;i<maxn;i++) pre[i]=i; return ; } int find(int x) { if(x==pre[x]) return x; else return pre[x]=find(pre[x]); } int join(int x,int y) { int f1=find(x); int f2=find(y); if(f1!=f2) { pre[f1]=f2; return 1; } return 0; } void Kruskal() { init(); sort(q+1,q+1+m,cmp); int cnt=0; for(int i=1;i<=m;i++) { if(join(q[i].u,q[i].v)) { vt[q[i].v].pb(mp(q[i].u,q[i].w)); vt[q[i].u].pb(mp(q[i].v,q[i].w)); cnt++; if(cnt==n-1) break; } } return ; } void dfs(int x,int p,int d) { parent[0][x]=p; depth[x]=d; for(int i=0;i<vt[x].size();i++) { int v=vt[x][i].first; if(v!=p) { dis[v][0]=vt[x][i].second; dfs(v,x,d+1); } } return ; } void initlca() { dfs(1,-1,0); kk=0; for(int i=1;;kk++)//求树的深度 { i<<=1; if(i>n) break; } for(int k=0;k<kk;k++) { for(int v=1;v<=n;v++) { if(parent[k][v]<0) parent[k+1][v]=-1; else { parent[k+1][v]=parent[k][parent[k][v]]; dis[v][k+1]=min(dis[v][k],dis[parent[k][v]][k]); } } } return ; } int lca(int u,int v) { ans=inf; if(depth[u]>depth[v]) swap(u,v); for(int k=0;k<=kk;k++) { if((depth[v]-depth[u])>>k&1) { ans=min(ans,dis[v][k]); v=parent[k][v]; } } if(u==v) return ans; for(int k=kk;k>=0;k--) { if(parent[k][v]!=parent[k][u]) { ans=min(ans,dis[u][k]); ans=min(ans,dis[v][k]); u=parent[k][u]; v=parent[k][v]; } } ans=min(ans,dis[u][0]); ans=min(ans,dis[v][0]); return ans; } int main() { Ri(n),Ri(m),Ri(qq); for(int i=1;i<=m;i++) Ri(q[i].u),Ri(q[i].v),Ri(q[i].w); Kruskal(); CLR(dis,inf); initlca(); W(qq) { int x,y; Ri(x),Ri(y); printf("%d\n",lca(x,y)); } return 0; } /* 4 5 3 1 2 6 1 3 8 2 3 4 2 4 5 3 4 7 2 3 1 4 3 4 */ Marcus-Bao 认证博客专家 推荐系统 ACM算法竞赛 机器学习 本科毕业于国内知名四非大学，现中国科学院大学博士生，中国科学院计算技术研究所vipl实验室，老年ACM铁牌退役选手，喜欢算法竞赛，会点数据结构和算法，熟悉c++，python等；现阶段研究方向主要为机器学习与数据挖掘，比较关注推荐系统，发过顶会，炼过丹，平时博客主要记录些关于算法、数据结构，人工智能技术以及平时看的论文总结分享等，欢迎大家关注我，一起多多交流共同进步！
