答案:<p style="text-align: left;">#include<iostream></p><p style="text-align: left;">#include<cstdio></p><p style="text-align: left;">#include<cstring></p><p style="text-align: left;">#include<cmath></p><p style="text-align: left;">#include<algorithm></p><p style="text-align: left;">#define _for(i,a,b) for (int i=a;i<=b;i++)</p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">const int N=1e4+5,M=5e4+5;//g[u][j]表示u到f[u][j]这条链上边权的最大值。</p><p style="text-align: left;">int n,m,fa[N],h[N],e[M],ne[M],w[M],idx,d[N],f[N][20],g[N][20];</p><p style="text-align: left;">struct node{</p><p style="text-align: left;"> int a,b,w;</p><p style="text-align: left;"> bool operator <(const node& rhs) const{</p><p style="text-align: left;"> return w>rhs.w;</p><p style="text-align: left;"> }</p><p style="text-align: left;">}a[M];</p><p style="text-align: left;">inline void c_plus(){//可以忽略</p><p style="text-align: left;"> ios::sync_with_stdio(false);</p><p style="text-align: left;"> cin.tie(0);</p><p style="text-align: left;"> cout.tie(0);</p><p style="text-align: left;">}</p><p style="text-align: left;">inline void init_list(){//单链表</p><p style="text-align: left;"> idx=0;</p><p style="text-align: left;"> memset(h,-1,sizeof(h));</p><p style="text-align: left;">}</p><p style="text-align: left;">inline void add(int a,int b,int c){//同上</p><p style="text-align: left;"> e[idx]=b;</p><p style="text-align: left;"> w[idx]=c;</p><p style="text-align: left;"> ne[idx]=h[a];</p><p style="text-align: left;"> h[a]=idx++;</p><p style="text-align: left;">}</p><p style="text-align: left;">inline void init_set(){//并查集</p><p style="text-align: left;"> _for(i,1,n){</p><p style="text-align: left;"> fa[i]=i;</p><p style="text-align: left;"> }</p><p style="text-align: left;">}</p><p style="text-align: left;">int get(int x){//同上</p><p style="text-align: left;"> if (x==fa[x]){</p><p style="text-align: left;"> return x;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> return fa[x]=get(fa[x]);</p><p style="text-align: left;">}</p><p style="text-align: left;">void kruskal(){//kruskal算法</p><p style="text-align: left;"> sort(a+1,a+m+1);</p><p style="text-align: left;"> _for(i,1,m){</p><p style="text-align: left;"> int x=get(a[i].a);</p><p style="text-align: left;"> int y=get(a[i].b);</p><p style="text-align: left;"> if (x!=y){</p><p style="text-align: left;"> fa[y]=x;</p><p style="text-align: left;"> add(a[i].a,a[i].b,a[i].w);</p><p style="text-align: left;"> add(a[i].b,a[i].a,a[i].w);</p><p style="text-align: left;"> }</p><p style="text-align: left;"> }</p><p style="text-align: left;">}</p><p style="text-align: left;">void dfs(int u){</p><p style="text-align: left;"><span style="white-space:pre"> </span>d[u]=d[f[u][0]]+1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for (int i=h[u];i!=-1;i=ne[i]){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int j=e[i];</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (j==f[u][0]){</p><p style="text-align: left;"><span style="white-space:pre"> </span>continue;</p><p style="text-align: left;"> }</p><p style="text-align: left;"><span style="white-space:pre"> </span>f[j][0]=u;</p><p style="text-align: left;"> g[j][0]=w[i];//我们需要在dfs函数里给g[v][0]赋初值,为每个结点v上面那条边的权值。</p><p style="text-align: left;"><span style="white-space:pre"> </span>dfs(j);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">}</p><p style="text-align: left;">int lca(int x,int y){//LCA算法</p><p style="text-align: left;"> if (get(x)!=get(y)){//判断是否合法,在不在一个连通块内</p><p style="text-align: left;"> return -1;</p><p style="text-align: left;"> }</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (d[x]<d[y]){</p><p style="text-align: left;"><span style="white-space:pre"> </span>swap(x,y);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>int k=(int)(log2(d[x])),ans=0x7fffffff;//ans存答案</p><p style="text-align: left;"><span style="white-space:pre"> </span>for (int j=k;j>=0;j--){</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (d[f[x][j]]>=d[y]){</p><p style="text-align: left;"> ans=min(ans,g[x][j]);//维护最大值</p><p style="text-align: left;"><span style="white-space:pre"> </span>x=f[x][j];</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (x==y){/</p><p style="text-align: left;"><span style="white-space:pre"> </span>goto output;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>k=(int)(log2(d[x]));</p><p style="text-align: left;"><span style="white-space:pre"> </span>for (int j=k;j>=0;j--){</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (f[x][j]!=f[y][j]){</p><p style="text-align: left;"> ans=min(ans,min(g[x][j],g[y][j]));//维护最大值</p><p style="text-align: left;"><span style="white-space:pre"> </span>x=f[x][j];</p><p style="text-align: left;"><span style="white-space:pre"> </span>y=f[y][j];</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"> ans=min(ans,min(g[x][0],g[y][0]));//最后还差一步才到达lca,因此还要算上最后两条边的最大值</p><p style="text-align: left;"> output:</p><p style="text-align: left;"><span style="white-space:pre"> </span>return ans;</p><p style="text-align: left;">}</p><p style="text-align: left;">int main(){</p><p style="text-align: left;"> freopen("truck.in","r",stdin);</p><p style="text-align: left;"> freopen("truck.out","w",stdout);</p><p style="text-align: left;"> c_plus();</p><p style="text-align: left;"> int q,x,y;</p><p style="text-align: left;"> cin>>n>>m;</p><p style="text-align: left;"> init_list();</p><p style="text-align: left;"> init_set();</p><p style="text-align: left;"> _for(i,1,m){</p><p style="text-align: left;"> cin>>a[i].a>>a[i].b>>a[i].w;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> kruskal();</p><p style="text-align: left;"> _for(i,1,n){</p><p style="text-align: left;"> if (d[i]==0){//每个连通块都要遍历</p><p style="text-align: left;"> dfs(i);</p><p style="text-align: left;"> }</p><p style="text-align: left;"> }</p><p style="text-align: left;"> for (int j=1;(1<<j)<=n;j++){</p><p style="text-align: left;"> _for(i,1,n){</p><p style="text-align: left;"> f[i][j]=f[f[i][j-1]][j-1];</p><p style="text-align: left;"> g[i][j]=min(g[i][j-1],g[f[i][j-1]][j-1]);//通过动态规划计算g数组剩余的值。</p><p style="text-align: left;">//转移方程很显然,就是把从i到f[i][j]这条链,拆成i到f[i][j-1]和f[i][j-1]到f[i][j]两条链,</p><p style="text-align: left;">//然后取最大值</p><p style="text-align: left;"> }</p><p style="text-align: left;"> }</p><p style="text-align: left;"> cin>>q;</p><p style="text-align: left;"> while (q--){</p><p style="text-align: left;"> cin>>x>>y;</p><p style="text-align: left;"> cout<<lca(x,y)<<endl;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。