一道最大生成树和LCA的结合问题。
有几个要注意的：
1.链式前向星不能直接排序，只能借助另一个结构体完成（详细见代码）
2.par，fa，w都要处理，其中par可以一开始就处理，而fa在dfs中处理，而w跟着fa一起更新即可。
剩下的就没什么了……
代码：
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; #define maxn 100005 #define INF 9999999 struct first { int x,y,z; } fir[5*maxn]; struct second { int to,nxt,w; } now[5*maxn]; int head[maxn],dep[maxn],par[maxn],fa[maxn][21],w[maxn][21]; int cnt,n,m,q; bool vis[maxn]; bool cmp(first a,first b) { return a.z>b.z; } void Deal_first() { sort(fir+1,fir+1+m,cmp); for(int i=1; i<=n; i++) par[i]=i; } void add(int a,int b,int c) { now[++cnt].to=b; now[cnt].nxt=head[a]; head[a]=cnt; now[cnt].w=c; } void dfs(int u,int father) { for(int i = 1;i <= 20;i++) fa[u][i] = fa[fa[u][i - 1]][i - 1],w[u][i] = min(w[u][i - 1],w[fa[u][i - 1]][i - 1]);//只能这么表示，总不能w[u][i]=w[u][i]吧； for(int i=head[u]; i; i=now[i].nxt) { int to = now[i].to; if(vis[to]) continue; dep[to] = dep[u] + 1; vis[to] = 1; fa[to][0] = u; w[to][0]=now[i].w; dfs(to,u); } return ; } int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); } void kruskal() { for(int i=1; i<=m; i++) { int u = fir[i].x,v = fir[i].y,w = fir[i].z; if(find(u) == find(v)) continue; par[find(u)]=find(v); add(u,v,w); add(v,u,w); } return ; } int lca(int x,int y) { if(find(x)!=find(y)) return -1; int ans=INF; if(dep[x]<dep[y]) swap(x,y); for(int i=20; i>=0; i--) { if(dep[fa[x][i]]>=dep[y]) { ans=min(ans,w[x][i]); x=fa[x][i]; } if(x==y) return ans; } for(int i=20; i>=0; i--) { if(fa[x][i]!=fa[y][i]) { ans=min(min(w[x][i],w[y][i]),ans); x=fa[x][i]; y=fa[y][i]; } } ans=min(ans,min(w[x][0],w[y][0])); return ans; } int main() { int x,y,z; memset(w,0x3f,sizeof(w)); scanf("%d%d",&n,&m); for(int i=1; i<=m; i++) { scanf("%d%d%d",&x,&y,&z); fir[i].x=x; fir[i].y=y; fir[i].z=z; } Deal_first(); kruskal(); for(int i=1; i<=n; i++) if(!vis[i]) { vis[i] = 1; dfs(i,0); } scanf("%d",&q); for(int i=1; i<=q; i++) { scanf("%d%d",&x,&y); printf("%d ",lca(x,y)); } return 0; }
最后希望这个题解能帮到大家>\<~~~