其实很简单。
先克鲁斯卡尔求最大生成树（生成出来的无根树要转为有根树）
其次输入X和Y，求X和Y的LCA（最近公共祖先）（这里如果并查集的祖先不同可以直接输出-1）
求LCA有很快的倍增算法，但是在这个地方其实不需要。窝就是先从X遍历到X的根节点，遍历的时候每遍历一个点就记录下来（这里一定要注意两端的点，即X和X的根节点，一定要标记，我被这个坑了好久）。再从Y向根节点遍历，一直遍历到某个已经标记过的点（在从X遍历到X的根节点时做的标记~），遍历的时候ans=min(ans,正在遍历的边的权值)（ans一开始设置为一个很大的数，如100000000），就是ans为所有从Y向根节点遍历所经过的边的权值中的最小值。然后遍历到某个标记过的点时，那个点就是我们要求的LCA，然后再从X向LCA遍历，遍历的时候依然是：ans=min(ans,正在遍历的边的权值)，然后输出ans

36行的C++AC代码：

#include <bits/stdc++.h>
using namespace std;
int n,m,q,x,y,ans,f[10005],pre[10005],cost[10005],cnt;bool book[10005];
int findf(int x){return f[x]==x?x:(f[x]=findf(f[x]));}
struct edge{int x,y,z;}ne;
bool edcmp(edge e1,edge e2){return e1.z>e2.z;}
vector<edge> eds;vector<pair<int,int> > tree[10005];
void build_tree(int u){for(vector<pair<int,int> >::iterator i=tree[u].begin();i!=tree[u].end();i++)if(!pre[i->first])pre[i->first]=u,cost[i->first]=i->second,build_tree(i->first);}
int main()
{
    ios::sync_with_stdio(0); 
    cin>>n>>m;
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=m;i++)cin>>ne.x>>ne.y>>ne.z,eds.push_back(ne);
    sort(eds.begin(),eds.end(),edcmp);
    for(vector<edge>::iterator i=eds.begin();cnt<n-1&&i!=eds.end();i++)
    {
        int fa[2]={findf(i->x),findf(i->y)}; 
        if(fa[0]!=fa[1])cnt++,tree[i->x].push_back(make_pair(i->y,i->z)),tree[i->y].push_back(make_pair(i->x,i->z)),f[fa[0]]=fa[1];
    }
    for(int i=1;i<=n;i++)if(!pre[i])pre[i]=i,build_tree(i);
    cin>>q;
    while(q--)
    {
        memset(book,0,sizeof(book)),ans=100000000;
        cin>>x>>y;if(findf(x)!=findf(y)){cout<<-1<<endl;continue;}
        int lca,j=x;
        do book[j]=1,j=pre[j];while(pre[j]!=j);
        book[j]=1,j=y;
        while(!book[j])ans=min(ans,cost[j]),j=pre[j];
        lca=j,j=x;
        while(j!=lca)ans=min(ans,cost[j]),j=pre[j];
        cout<<ans<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

struct node{
    int x,y,z;
    friend bool operator <(const node& x,const node& y) {
        return x.z>y.z;
    }
} edge[50005];
int n,m,Q,f[10005],ans[50005];
set<int> q[10005];

inline int find(int x) {
    while (x!=f[x]) x=f[x]=f[f[x]];
    return x;
}

int main() {
    memset(ans,-1,sizeof(ans));
    scanf("%d%d",&n,&m);
    for (int i=0;i<m;i++) scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z);
    sort(edge,edge+m);
    scanf("%d",&Q);
    for (int i=1;i<=Q;i++) {
        int x,y; scanf("%d%d",&x,&y);
        q[x].insert(i);
        q[y].insert(i);
    }
    for (int i=1;i<=n;i++) f[i]=i; 
    for (int i=0;i<m;i++) {
        int findx=find(edge[i].x),findy=find(edge[i].y);
        if (findx==findy) continue;
        if (q[findx].size()>q[findy].size()) swap(findx,findy);
        for (set<int>::iterator it=q[findx].begin();it!=q[findx].end();it++) {
            int cur=*it;
            if (!q[findy].count(cur)) q[findy].insert(cur);
            else {
                ans[cur]=edge[i].z;
                q[findy].erase(cur);
            }
        }
        f[findx]=findy;
    }
    for (int i=1;i<=Q;i++) printf("%d\n",ans[i]);
    return 0;
}

先更新边权，再更新倍增点（bug调了五分钟）

应该是入OI以来写的最长的代码了，比某些BFS/DFS代码还长....

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 2e4+7;
const int MAXM = 1e5+7;

int n, m, qy;
int origfrom[MAXM], origto[MAXM], origl[MAXM], origid[MAXM];
// adjacent table
int ecnt;
int first[MAXN], nxt[MAXN], to[MAXN], l[MAXN];
// Union find set
int ufs[MAXN];
// LCA
int tlog;
int f[MAXN][20], fl[MAXN][20];
int d[MAXN], v[MAXN];

int lcainit(int a){
  queue<int> q;
  d[a] = 1;
  q.push(a);
  while(!q.empty()){
    int x = q.front();
    q.pop();
    if(v[x]) continue;
    // cout << x << " ";
    v[x] = 1;
    for(int e=first[x]; e!=0; e=nxt[e]){
      int y = to[e];
      if(!v[y]){
        d[y] = d[x]+1;
        f[y][0] = x;
        fl[y][0] = l[e];
        for(int i=1; i<=tlog; i++){
          f[y][i] = f[f[y][i-1]][i-1];
          fl[y][i] = min(fl[y][i-1], fl[f[y][i-1]][i-1]);
        }
        q.push(y);
      }
    }
  }
}

int lca(int a, int b){
  int ans = INF;
  if(d[a] < d[b]) swap(a, b);
  // cout << a << " ";
  for(int i=tlog; i>=0; i--){
    if(d[f[a][i]] >= d[b]){
      // cout << i << " " << fl[a][i] << endl;
      ans = min(ans, fl[a][i]);
      a = f[a][i];
    }
  }
  if(a == b){
    // return a;
    return ans;
  }
  for(int i=tlog; i>=0; i--){
    if(f[a][i] != f[b][i]){
      ans = min(ans, fl[a][i]);
      a = f[a][i];
      ans = min(ans, fl[b][i]);
      b = f[b][i];
    }
  }
  ans = min(ans, fl[a][0]);
  ans = min(ans, fl[b][0]);
  return ans;
  // return f[a][0];
}

bool cmp(int a, int b){
  return origl[a] > origl[b];
}

void init(int n){
  for(int i=0; i<=n; i++){
    ufs[i] = i;
  }
  return;
}

int find(int a){
  int root, ta = a, tta = a;
  while(ta != ufs[ta]){
    ta = ufs[ta];
  }
  root = ta;
  while(ta != ufs[ta]){
    tta = ta;
    ta = ufs[ta];
    ufs[tta] = root;
  }
  return root;
}

void unite(int a, int b){
  int roota = find(a), rootb = find(b);
  ufs[roota] = rootb;
  return;
}

bool sameufs(int a, int b){
  return find(a) == find(b);
}

void add_edge(int tfrom, int tto, int tl){
  ++ecnt;
  nxt[ecnt] = first[tfrom];
  first[tfrom] = ecnt;
  to[ecnt] = tto;
  l[ecnt] = tl;
  return;
}

int main(){
  // freopen("1967.txt", "r", stdin);
  int tfrom, tto, tl;
  scanf("%d%d", &n, &m);
  tlog = (int) log(n)/log(2) + 1;
  init(n);
  for(int i=0; i<m; i++){
    scanf("%d%d%d", &origfrom[i], &origto[i], &origl[i]);
    origid[i] = i;
  }
  sort(origid, origid+m, cmp);
  for(int i=0; i<m; i++){
    int ti = origid[i];
    if(!sameufs(origfrom[ti], origto[ti])){
      unite(origfrom[ti], origto[ti]);
      // cout << origfrom[ti] << " " << origto[ti] << " " << origl[ti] << endl;
      add_edge(origfrom[ti], origto[ti], origl[ti]);
      add_edge(origto[ti], origfrom[ti], origl[ti]);
    }
  }
  memset(fl, 0x3f, sizeof(fl));
  for(int i=1; i<=n; i++){
    if(!d[i]){
      lcainit(i);
    }
  }
  // for(int i=1; i<=n; i++){
  //   for(int j=0; j<=tlog; j++){
  //     cout << fl[i][j] << " " ;
  //   }
  //   cout << endl;
  // }
  scanf("%d", &qy);
  for(int i=0; i<qy; ++i){
    scanf("%d %d", &tfrom, &tto);
    if(sameufs(tfrom, tto)){
      printf("%d\n", lca(tfrom, tto));
    }else{
      printf("%d\n", -1);
    }
  }

  return 0;
}

评测情况

真的有点慢了

 Accepted
/in/foo.cc: In function 'int lcainit(int)':
/in/foo.cc:49:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
/in/foo.cc: In function 'int main()':
/in/foo.cc:126:19: warning: unused variable 'tl' [-Wunused-variable]
   int tfrom, tto, tl;
                   ^~
#   状态  耗时  内存占用
#1   Accepted   6ms 4.344 MiB
#2   Accepted   5ms 5.125 MiB
#3   Accepted   15ms    3.715 MiB
#4   Accepted   16ms    3.621 MiB
#5   Accepted   21ms    4.117 MiB
#6   Accepted   15ms    4.75 MiB
#7   Accepted   61ms    4.402 MiB
#8   Accepted   64ms    4.25 MiB
#9   Accepted   62ms    4.168 MiB
#10  Accepted   73ms    4.656 MiB
#11  Accepted   62ms    4.293 MiB
#12  Accepted   49ms    4.75 MiB
#13  Accepted   534ms   4.879 MiB
#14  Accepted   402ms   5.062 MiB
#15  Accepted   424ms   5.141 MiB
#16  Accepted   385ms   4.422 MiB
#17  Accepted   513ms   4.75 MiB
#18  Accepted   378ms   4.445 MiB
#19  Accepted   336ms   4.375 MiB
#20  Accepted   349ms   5.246 MiB

不用倍增
暴力lca完全没问题
各种模板套起来

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m;
int fa[10010];
struct edge{
    int q,z,v;
}a[50010];
int fi[10010],ne[50010],to[50010],w[50010];
int father[10010];
int e=0;
int deep[10010];
int road[10010];
int ans=99999999;
void build(int x,int y,int z)
{
    e++;
    to[e]=y;
    w[e]=z;
    ne[e]=fi[x];
    fi[x]=e;
}
int cmp(const edge &x,const edge &y)
{
    return x.v>y.v;
}
int find(int x)
{
    if(x==fa[x]) return x;
    else return fa[x]=find(fa[x]);
}
void kel()
{
    int k=0;
    for(int i=1;i<=m&&k<n;i++)
    {
        if(k==n-1) break;
        if(find(a[i].q)!=find(a[i].z))
        {
            k++;
            fa[find(a[i].q)]=find(a[i].z);                                                          
            build(a[i].q,a[i].z,a[i].v);
            build(a[i].z,a[i].q,a[i].v);
        }
    }
    return;
}

int dfs(int x,int dep,int root)
{
    deep[x]=dep;
    for(int i=fi[x];i>0;i=ne[i])
    {
        if(deep[to[i]]!=0||to[i]==root) continue;
        else
        {
            father[to[i]]=x;
            road[to[i]]=w[i];
            dfs(to[i],dep+1,root);
        }
    }
}


int lca(int x,int y)
{
    if(find(x)!=find(y)) 
    {
        ans=-1;
    }
    else
    {
        ans=99999999;
      while(deep[x]>deep[y]) 
      {
        ans=min(ans,road[x]);
        x=father[x];
      }
      while(deep[x]<deep[y])
      {
        ans=min(ans,road[y]);
        y=father[y];
      } 
      while(x!=y)
      {
        ans=min(ans,road[x]);
        ans=min(ans,road[y]);
        x=father[x];
        y=father[y];
      } 
    }
    return ans;
}
int main()
{
    memset(road,0x3f,sizeof(road));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) 
    {
        fa[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a[i].q,&a[i].z,&a[i].v);
    }
    sort(a+1,a+m+1,cmp);
    kel();
    for(int i=1;i<=n;i++)
     if(fa[i]==i) 
     {
        father[i]=i;
        dfs(i,0,i);
     }
    int q,x,y;
    scanf("%d",&q);
    int ans;
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&x,&y);
        ans=lca(x,y);
        printf("%d\n",ans);
    }
    return 0;
}

重点在于把思路理清，思想都在代码里了，请笑纳。
```cpp
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Dor(i,l,r) for(int i=l;i>=r;i--)
#define N 10005
#define M 50005
#define ll long long
using namespace std;

struct node{
int u,v,val;
}a[M];

//核心：求最大生成树，然后利用倍增算法求最值，复杂度O（nlogn）
int w[N*2],to[N*2],head[N*2],nxt[N*2],cnt=0,f[N];
int n,m,dep[N],fa[N][25],val[N][25],tlog;
//添边
void add(int u,int v,int cost)
{
nxt[++cnt]=head[u];
head[u]=cnt;
w[cnt]=cost;
to[cnt]=v;
}
//并查集
int getf(int x){
if (x==f[x]) return x;
f[x]=getf(f[x]);
return f[x];
}
void combine(int x,int y){
x=getf(x);
y=getf(y);
f[x]=y;
}
bool query(int x,int y){
x=getf(x);
y=getf(y);
return (x==y);
}
bool cmp(node a,node b){
return a.val>b.val;
}
//求最大生成树
void Kruskal(){
int rest=n-1;
For(i,1,m){
if (!rest) break;
if (!query(a[i].u,a[i].v)){
combine(a[i].u,a[i].v);
add(a[i].u,a[i].v,a[i].val);
add(a[i].v,a[i].u,a[i].val);
rest--;
}
}
}
//遍历深度
void dfs(int t,int f){
dep[t]=dep[f]+1;fa[t][0]=f;
for(int i=head[t];i;i=nxt[i]){
if (to[i]!=f){
val[to[i]][0]=w[i];
dfs(to[i],t);
}
}

}
void init(){
dfs(1,0);
For(j,0,tlog){
For(i,1,n){
fa[i][j+1]=fa[fa[i][j]][j];
val[i][j+1]=min(val[i][j],val[fa[i][j]][j]);//存储最值
}
}
}
//倍增求lca和最值
int lca(int x,int y){
int ans=2100000000;
if (!query(x,y)) return -1;
if (dep[x]<dep[y]) swap(x,y);
Dor(j,tlog,0) if (dep[fa[x][j]]>=dep[y]){
ans=min(ans,val[x][j]);
x=fa[x][j];
}
Dor(j,tlog,0) if (fa[x][j]!=fa[y][j]){
ans=min(ans,val[x][j]);
ans=min(ans,val[y][j]);
x=fa[x][j],y=fa[y][j];
}
if (x!=y)
{
ans=min(ans,val[x][0]),ans=min(ans,val[y][0]);
x=fa[x][0],y=fa[y][0];
}
return ans;
}
int main(){
memset(val,127/3,sizeof(val));
scanf("%d%d",&n,&m);
For(i,1,m){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
a[i].u=x,a[i].v=y,a[i].val=z;
}

For(i,1,n) f[i]=i;
tlog= (int)log(n)/log(2)+1;
sort(a+1,a+m+1,cmp);
Kruskal();
init();
int q;
scanf("%d",&q);
For(i,1,q){
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",lca(x,y));
}
return 0;
}
```

先用Kruskal算法求出最大生成树，然后LCA时求限重最小值。

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int n, m, q;

int parent[10001];
int depth[10001];

int ancestor[10001][15];
int minweight[10001][15];

struct FullRoad {
    int x;
    int y;
    int z;
};

FullRoad full_roads[50001];

bool cmp(FullRoad a, FullRoad b)
{
    return a.z > b.z;
}

struct Road {
    int y;
    int z;
};
vector<Road> conn[10001];

int uf[10001];

int uf_find(int a)
{
    if (uf[a] == a) return a;
    uf[a] = uf_find(uf[a]);
    return uf[a];
}

void uf_union(int a, int b)
{
    a = uf_find(a);
    b = uf_find(b);
    uf[a] = b;
}

void mk_tree(int node, int p, int d, int wt)
{
    if (parent[node] != 0) return;
    parent[node] = p;
    depth[node] = d;
    minweight[node][0] = wt;
    for (int i = 0; i < conn[node].size(); i++) {
        mk_tree(conn[node][i].y, node, d + 1, conn[node][i].z);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        uf[i] = i;
    }
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        full_roads[i].x = x;
        full_roads[i].y = y;
        full_roads[i].z = z;
    }
    sort(full_roads + 1, full_roads + m + 1, cmp);
    for (int i = 1; i <= m; i++) {
        int x = full_roads[i].x;
        int y = full_roads[i].y;
        int z = full_roads[i].z;
        if (uf_find(x) != uf_find(y)) {
            uf_union(x, y);
            Road r;
            r.y = y;
            r.z = z;
            conn[x].push_back(r);
            r.y = x;
            conn[y].push_back(r);
        }
    }
    for (int i = 1; i <= n; i++) {
        mk_tree(i, -1, 0, -1);
        ancestor[i][0] = parent[i];
    }
    for (int i = 1; i <= 14; i++) {
        for (int j = 1; j <= n; j++) {
            ancestor[j][i] = ancestor[j][i-1];
            if (ancestor[j][i] != -1) ancestor[j][i] = ancestor[ancestor[j][i-1]][i-1];
            minweight[j][i] = min(minweight[j][i-1], minweight[ancestor[j][i-1]][i-1]);
        }
    }
    scanf("%d", &q);
    for (int i = 1; i <= q; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        int ans = 2000000000;
        if (uf_find(x) != uf_find(y)) {
            printf("-1\n");
            continue;
        }
        if (depth[x] > depth[y]) {
            int t = x;
            x = y;
            y = t;
        }
        for (int i = 0; i <= 14; i++) {
            if ((depth[y] - depth[x]) & (1 << i)) {
                ans = min(ans, minweight[y][i]);
                y = ancestor[y][i];
            }
        }
        if (x == y) {
            printf("%d\n", ans);
            continue;
        }
        for (int i = 14; i >= 0; i--) {
            if (ancestor[x][i] != ancestor[y][i]) {
                ans = min(ans, minweight[x][i]);
                ans = min(ans, minweight[y][i]);
                x = ancestor[x][i];
                y = ancestor[y][i];
            }
        }
        ans = min(ans, minweight[x][0]);
        ans = min(ans, minweight[y][0]);
        printf("%d\n", ans);
    }
    return 0;
}

先用kruskal求最大生成树
再对每次询问在最大生成树上求他们到lca路径中的最小边权。倍增求lca，注意先更新最小边权再更新x和y(被这个坑了2个小时。。)
AC代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn=1e4+10;
const int inf=0x3f3f3f3f;
struct edge{
    int from,nxt,to,w;
}e[maxn*20],ed[maxn*10];
int last[maxn],cnt,n,m,dep[maxn],f[maxn][25],c[maxn][25],fa[maxn];
vector<int> Set_of_edge;
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
inline void insert(int u,int v,int c)
{
    e[++cnt]=(edge){u,last[u],v,c};last[u]=cnt;
    e[++cnt]=(edge){v,last[v],u,c};last[v]=cnt;
}
inline void dfs(int cur,int pre)
{
    f[cur][0]=pre,dep[cur]=dep[pre]+1;
    for(register int i=1;i<=20;i++)
    {
        f[cur][i]=f[f[cur][i-1]][i-1];
        c[cur][i]=min(c[f[cur][i-1]][i-1],c[cur][i-1]);
    }
    for(register int i=last[cur];i;i=e[i].nxt)
    {
        register int v=e[i].to;
        if(v==pre) continue;
        c[v][0]=e[i].w;
        dfs(v,cur);
    }
}
inline int lca(int x,int y)
{
    int ret=inf;
    if(x==y) return 0;
    if(dep[x]<dep[y])swap(x,y);
    for(register int i=20;i>=0;i--)
    {
        if((dep[x]-dep[y])>=(1<<i)) ret=min(ret,c[x][i]),x=f[x][i];
    }
    if(x==y) return ret;
    for(register int i=20;i>=0;i--)
    {
        if(f[x][i]!=f[y][i])
        {
            ret=min(min(c[x][i],c[y][i]),ret);
            x=f[x][i],y=f[y][i];
        }
    }
    if(x==y) return ret;
    return min(min(c[x][0],c[y][0]),ret);
}
inline bool comp(const edge &a,const edge &b)
{
    return a.w>b.w;
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read(),c=read();
        ed[i].from=u,ed[i].to=v,ed[i].w=c;
    }
    sort(ed+1,ed+1+m,comp);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(register int i=1;i<=m;i++)
    {
        int fx=find(ed[i].from),fy=find(ed[i].to);
        if(fx==fy) continue;
        Set_of_edge.push_back(i),fa[fx]=fy;
    }
    for(register int i=0;i<Set_of_edge.size();i++)
        insert(ed[Set_of_edge[i]].from,ed[Set_of_edge[i]].to,ed[Set_of_edge[i]].w);
    dep[1]=1;
    dfs(1,0);
    int q=read();
    while(q--)
    {
        int s=read(),t=read();
        if(find(s)!=find(t)){puts("-1");continue;}
        printf("%d\n",lca(s,t));
    }
    return 0;
}

// 最大生成树 lca 时维护min_len.

uses math;
type
    re=record
        v,len,next:longint;
    end;
    rea=record
        u,v,len:longint;
    end;

var
    n,m,q,u,v,z,i,tot,x,y,max_deep,ans:longint;
    father,deep,last:array[0..10000]of longint;
    flag:array[0..10000]of boolean;
    f,min_len:array[0..10000,0..14]of longint;
    g:array[0..50000]of rea;
    t:array[0..10000*2]of re;

procedure add(u,v,z:longint);
begin
    inc(tot);
    t[tot].v:=v;
    t[tot].len:=z;
    t[tot].next:=last[u];
    last[u]:=tot;
end;

function find(i:longint):longint;
begin
    if father[i]=i then exit(i);
    father[i]:=find(father[i]);
    exit(father[i]);
end;

procedure sort(l,r:longint);
var
    i,j,x:longint;
    y:rea;
begin
    i:=l; j:=r;
    x:=g[(l+r) div 2].len;
    repeat
        while g[i].len>x do inc(i);
        while x>g[j].len do dec(j);
        if not(i>j) then
        begin
            y:=g[i]; g[i]:=g[j]; g[j]:=y;
            inc(i); j:=j-1;
        end;
    until i>j;
    if l<j then sort(l,j);
    if i<r then sort(i,r);
end;

procedure Kruskal;
var
    i,j,x,y:longint;
begin
    sort(1,m);
    for i:=1 to n do father[i]:=i;
    for i:=1 to m do
    begin
        x:=find(g[i].u); y:=find(g[i].v);
        if x<>y then
                begin
                        father[x]:=y;
                        add(g[i].u,g[i].v,g[i].len); add(g[i].v,g[i].u,g[i].len);
                end;
    end;
end;

procedure Dfs_t(i,fat:longint);
var
    x,tox:longint;
begin
        x:=last[i];
    while x<>0 do
    begin
        tox:=t[x].v;
                if tox<>fat then
                begin
                flag[tox]:=true;
                    deep[tox]:=deep[i]+1;
                max_deep:=max(max_deep,deep[tox]);
                f[tox][0]:=i;
                min_len[tox][0]:=t[x].len;
                        Dfs_t(tox,i);
                end;
        x:=t[x].next;
    end;
end;

procedure Init_f;
var
    i,j:longint;
begin
    for j:=1 to trunc(ln(max_deep)/ln(2)) do
        for i:=1 to n do
            if deep[i]<<j>=1 then
            begin
                f[i][j]:=f[f[i][j-1]][j-1];
                min_len[i][j]:=min(min_len[i][j-1],min_len[f[i][j-1]][j-1]);
            end;
end;

procedure Init;
var
    i,j:longint;
begin
    readln(n,m);
    for i:=1 to m do readln(g[i].u,g[i].v,g[i].len);
    Kruskal;
    for i:=1 to n do
        if not flag[i] then Dfs_t(i,0);
    Init_f;
end;

procedure swap(var x,y:longint);
var
        cmp:longint;
begin
        cmp:=x; x:=y; y:=cmp;
end;

function lca(x,y:longint):longint;
var
    k,p:longint;
begin
    if deep[x]<deep[y] then swap(x,y);
    p:=deep[x]-deep[y]; k:=0;
    while p<>0 do
    begin
        if (p and 1=1) then
        begin
                        ans:=min(ans,min_len[x][k]);
            x:=f[x][k];
        end;
        inc(k);
        p:=p>>1;
    end;
    if x=y then exit;
    k:=0;
    while k>=0 do
    begin
        if f[x][k]<>f[y][k] then
        begin
            ans:=min(ans,min_len[x][k]);
            ans:=min(ans,min_len[y][k]);
            x:=f[x][k];
            y:=f[y][k];
            inc(k);
        end else dec(k);
    end;
    ans:=min(ans,min_len[x][0]);
        ans:=min(ans,min_len[y][0]);
end;

begin
    Init;
    read(q);
    for i:=1 to q do
    begin
        readln(u,v);
        x:=find(u); y:=find(v);
        if x<>y then writeln(-1) else
        begin
            ans:=maxlongint;
            lca(u,v);
            writeln(ans);
                end;
    end;
end.

我加了一个超级根，就是从编号为0的超级根向其他所有点连一个权为-1的路，再做最大生成树
然后我就一直wa，wa了4个小时
最后我发现，保存边的数组大小不应该是50000，因为我还引进了好多-1的边，应该开60000（= 10000 + 50000）的数组
我的青春啊！！！！就这么浪费了！！！

测试数据 #0: Accepted, time = 15 ms, mem = 5968 KiB, score = 5

测试数据 #1: Accepted, time = 0 ms, mem = 5972 KiB, score = 5

测试数据 #2: Accepted, time = 15 ms, mem = 5968 KiB, score = 5

测试数据 #3: Accepted, time = 0 ms, mem = 5972 KiB, score = 5

测试数据 #4: Accepted, time = 15 ms, mem = 5968 KiB, score = 5

测试数据 #5: Accepted, time = 0 ms, mem = 5968 KiB, score = 5

测试数据 #6: Accepted, time = 46 ms, mem = 5968 KiB, score = 5

测试数据 #7: Accepted, time = 62 ms, mem = 5968 KiB, score = 5

测试数据 #8: Accepted, time = 62 ms, mem = 5972 KiB, score = 5

测试数据 #9: Accepted, time = 46 ms, mem = 5964 KiB, score = 5

测试数据 #10: Accepted, time = 78 ms, mem = 5972 KiB, score = 5

测试数据 #11: Accepted, time = 46 ms, mem = 5968 KiB, score = 5

测试数据 #12: Accepted, time = 78 ms, mem = 5972 KiB, score = 5

测试数据 #13: Accepted, time = 78 ms, mem = 5968 KiB, score = 5

测试数据 #14: Accepted, time = 109 ms, mem = 5968 KiB, score = 5

测试数据 #15: Accepted, time = 93 ms, mem = 5972 KiB, score = 5

测试数据 #16: Accepted, time = 93 ms, mem = 5968 KiB, score = 5

测试数据 #17: Accepted, time = 62 ms, mem = 5972 KiB, score = 5

测试数据 #18: Accepted, time = 78 ms, mem = 5968 KiB, score = 5

测试数据 #19: Accepted, time = 78 ms, mem = 5968 KiB, score = 5

Accepted, time = 1054 ms, mem = 5972 KiB, score = 100
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
struct SortNode{
int x,y,cap;
};
struct Edge{
int to,next,cap;
};
int min(int x,int y){
if(x>=y) return y;
return x;
}
Edge edges[100000];
int cnt;
int pos[10050];
int depth[10050];
int fa[10050];
int father[10050][32];
int d[10050][32];
int root,maxdepth;
int n,m;
int dfs_flag[10000];
SortNode s[100000];
int MST[100000];
void addedge(int x,int y,int cap){
cnt++;
edges[cnt].to=y;
if(pos[x]!=0)
edges[cnt].next=edges[pos[x]].next;
edges[pos[x]].next=cnt;
edges[cnt].cap=cap;
if(pos[x]==0)
pos[x]=cnt;
}
int cmp(const SortNode& a,const SortNode& b){
return a.cap>b.cap;
}
void dfs(int v,int dep){
if(dep>maxdepth)
maxdepth=dep;
dfs_flag[v]=1;
int x=pos[v];
depth[v]=dep;
while(x>0){
if(!dfs_flag[edges[x].to]){
dfs(edges[x].to,dep+1);
father[edges[x].to][0]=v;
d[edges[x].to][0]=edges[x].cap;
}
x=edges[x].next;
}
}
void init(){
int log=0;
for(;(1<<log)<maxdepth;log++);
for(int j=1;j<=log;j++){
for(int i=1;i<=m;i++){
if(depth[i]>=(1<<j)){
father[i][j]=father[father[i][j-1]][j-1];
d[i][j]=min(d[i][j-1],d[father[i][j-1]][j-1]);
}
}
}
}
int jump_to(int x,int dep,int &mincap){
int p=depth[x]-dep;
for(int j=0;(1<<j)<=p;j++){
if((1<<j)&p){
mincap=min(mincap,d[x][j]);
x=father[x][j];
}
}
return x;
}
int getfather(int x){
if(fa[x]==x){
return x;
}
fa[x]=getfather(fa[x]);
return fa[x];
}
int get(int x,int y){
if(getfather(x)!=getfather(y))
return -1;
int mincap=2100000000;
if(depth[x]>depth[y])

x=jump_to(x,depth[y],mincap);
else
y=jump_to(y,depth[x],mincap);
if(x==y) return mincap;
int j=0;
while(father[x][0]!=father[y][0]){
j=0;
for(;depth[x]>=(1<<j);j++){
if(father[x][j+1]==father[y][j+1])
break;
}
mincap=min(mincap,d[x][j]);
mincap=min(mincap,d[y][j]);
x=father[x][j];y=father[y][j];

}
mincap=min(mincap,d[x][0]);
mincap=min(mincap,d[y][0]);
return mincap;
}
int main(int argc, char** argv) {
//freopen("lca.in","r",stdin);
//freopen("lca.out","w",stdout);
cnt=0;
memset(edges,0,sizeof(edges));
memset(depth,0,sizeof(depth));
memset(father,0,sizeof(father));
memset(pos,0,sizeof(pos));
memset(dfs_flag,0,sizeof(dfs_flag));
memset(s,0,sizeof(s));
memset(MST,0,sizeof(MST));
memset(d,127,sizeof(d));
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)
{
fa[i]=i;
}
cnt=0;
for(int i=1;i<=n;i++){
int x,y,cap;
scanf("%d%d%d",&x,&y,&cap);
cnt++;
s[cnt].x=x;
s[cnt].y=y;
s[cnt].cap=cap;
}
sort(s+1,s+n+1,cmp);
for(int i=1;i<=n;i++){
int x=getfather(s[i].x);
int y=getfather(s[i].y);
if(x!=y){
MST[i]=1;
fa[x]=y;
}
}
cnt=0;
for(int i=1;i<=n;i++){
if(MST[i]){
addedge(s[i].y,s[i].x,s[i].cap);
addedge(s[i].x,s[i].y,s[i].cap);
}
}
for(int i=1;i<=m;i++){
if(!dfs_flag[i])
dfs(i,0);
}
init();

int q;
scanf("%d",&q);
int x,y;
for(int i=1;i<=q;i++){
scanf("%d%d",&x,&y);
printf("%d\n",get(x,y));
}
return 0;
}

太tm容易错了
6次RE

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int N=100000+100;
const int M=100000+100;
int fa[N][21];
int deep[N],flag[N],flag1[N];
int p[N],w[N],father[N];
int b[N],a[N],_next[N];
int d[N][21];
int n,m,tcase,root,nn;

struct node
{
int l,r,w;
}q[M];

void add(int x,int y,int z)
{
nn++;
a[nn]=x;
b[nn]=y;
w[nn]=z;
_next[nn]=p[x];
p[x]=nn;
nn++;
a[nn]=y;
b[nn]=x;
w[nn]=z;
_next[nn]=p[y];
p[y]=nn;
}

void dfs(int x,int height)
{
flag[x]=1;
for(int i=1;i<=20;i++)
{
if(deep[x]<(1<<i)) break;
fa[x][i]=fa[fa[x][i-1]][i-1];
d[x][i]=min(d[x][i-1],d[fa[x][i-1]][i-1]);
}
int e=p[x];
while(e>0)
{
int k=b[e];
if(!flag[k])
{
deep[k]=deep[x]+1;
fa[k][0]=x;
d[k][0]=w[e];
dfs(k,height+1);
}
e=_next[e];
}
}

int ask(int x,int y)
{
if(deep[x]<deep[y]) swap(x,y);
int t=deep[x]-deep[y];
for(int i=20;i>=0;i--)
{
if((1<<i)&t)
x=fa[x][i];
}
for(int i=20;i>=0;i--)
if(fa[x][i]!=fa[y][i])
{
x=fa[x][i];
y=fa[y][i];
}

if(x==y) return x;
return fa[x][0];
}

int query(int x,int f)
{
int minv=1<<29;
int t=deep[x]-deep[f];
for(int i=20;i>=0;i--)
{
if(t&(1<<i))
{
minv=min(minv,d[x][i]);
x=fa[x][i];
}
}
return minv;
}

int findf(int x)
{
if(father[x]==x) return x;
father[x]=findf(father[x]);
return father[x];
}

int merget(int x,int y)
{
x=findf(x);
y=findf(y);
father[x]=y;
}

int cmp(node x,node y)
{
return x.w>y.w;
}

void init()
{
int num=0;
sort(q+1,q+1+m,cmp);
for(int i=1;i<=m;i++)
{
int fx=findf(q[i].l),fy=findf(q[i].r);
if(fy!=fx)
{
add(q[i].l,q[i].r,q[i].w);
add(q[i].r,q[i].l,q[i].w);
father[fx]=fy;
num++;
if(num==n-1) break;
}
}
}

int main()
{
memset(d,127/3,sizeof(d));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
father[i]=i;
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].w);
}
init();
int p;
scanf("%d",&p);
for(int i=1;i<=p;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(findf(x)!=findf(y))
{
cout<<-1<<endl; continue;
}
else
{
for(int i=1;i<=n;i++) if(!flag[i]) dfs(i,1);
int t=ask(x,y);
int xx=query(x,t);
int yy=query(y,t);
printf("%d\n",min(xx,yy));
}
}
return 0;
}

用LCA+最大生成树就AC了，提交了一次就AC了，稀里糊涂就AC了，刚刚还在犯困
程序186行
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <string.h>
#include <functional>
using namespace std;
//此题目先求最大生成树然后计算LCA即可
#define MAXNUM 20000
#define MAXEDGE 60000
#define MAXLIMIT 20
typedef struct EDGE{
int x;
int y;
int w;
}EDGE;
class UnionSet{
private:
int dat[MAXNUM];
public:
void Init(int n)
{
int i;
for (i = 1; i <= n; i++)
{
dat[i] = i;
}
}
int Find(int x)
{
if (dat[x] == x)
{
return x;
}
return dat[x] = Find(dat[x]);
}
void Union(int x, int y)
{
dat[Find(x)] = Find(y);
}
};
EDGE edge[MAXEDGE];
vector<EDGE> point[MAXNUM];
int dis[MAXNUM];
int p[MAXNUM][MAXLIMIT + 1];
int w[MAXNUM][MAXLIMIT + 1];
bool v[MAXNUM];
queue<int> curpoint;
queue<int> disq;
UnionSet s;
int n, m;
bool cmp(const EDGE &x, const EDGE &y)
{
return x.w > y.w;
}
void kruskal()
{
int i;
sort(edge, edge + m, cmp);
s.Init(n);
for (i = 0; i < m; i++)
{
if (s.Find(edge[i].x) != s.Find(edge[i].y))
{
s.Union(edge[i].x, edge[i].y);
point[edge[i].x].push_back(edge[i]);
swap(edge[i].x, edge[i].y);
point[edge[i].x].push_back(edge[i]);
}
}
}
void lca_init()
{
int cur;
int i, j;
curpoint.push(1);
dis[1] = 0;
v[1] = false;
while (!curpoint.empty())
{
cur = curpoint.front();
curpoint.pop();
for (i = 0; i < point[cur].size(); i++)
{
if (v[point[cur][i].y])
{
v[point[cur][i].y] = false;
dis[point[cur][i].y] = dis[cur] + 1;
p[point[cur][i].y][0] = cur;
w[point[cur][i].y][0] = point[cur][i].w;
curpoint.push(point[cur][i].y);
}
}
}
for (j = 1; j <= MAXLIMIT; j++)
{
for (i = 1; i <= n; i++)
{
p[i][j] = p[p[i][j - 1]][j - 1];
w[i][j] = min(w[i][j - 1], w[p[i][j - 1]][j - 1]);
}
}
}
int lca(int x, int y)
{
int i;
int wx;
int wy;
wx = 1000000000;
wy = 1000000000;
if (dis[x] < dis[y])
{
swap(x, y);
}
if (dis[x]>dis[y])
{
for (i = MAXLIMIT; i >= 0; i--)
{
if (dis[p[x][i]] > dis[y])
{
wx = min(wx, w[x][i]);
x = p[x][i];
}
}
wx = min(wx, w[x][0]);
x = p[x][0];
}
if (x != y)
{
for (i = MAXLIMIT; i >= 0; i--)
{
if (p[x][i] != p[y][i])
{
wx = min(wx, w[x][i]);
x = p[x][i];
wy = min(wy, w[y][i]);
y = p[y][i];
}
}
wx = min(wx, w[x][0]);
x = p[x][0];
wy = min(wy, w[y][0]);
y = p[y][0];
}
return min(wx , wy);
}
int main()
{
int i, j;
int x, y, w;
int cur;
int q;
memset(dis, 0, sizeof(dis));
memset(p, 0, sizeof(p));
memset(v, true, sizeof(v));
scanf("%d%d", &n, &m);
for (i = 0; i < m; i++)
{
scanf("%d%d%d", &x, &y, &w);
if (x>y)
{
swap(x, y);
}
edge[i].x = x;
edge[i].y = y;
edge[i].w = w;
}
kruskal();
lca_init();
scanf("%d", &q);
for (i = 0; i < q; i++)
{
scanf("%d%d", &x, &y);
if (s.Find(x) != s.Find(y))
{
printf("-1\n");
}
else
{
printf("%d\n", lca(x, y));
}
}
return 0;
}

写LCA先处理w ， 再处理父节点 ， 不知为此WA了多少次
（ 其实一调试就看出来了 ， 本人比较懒。。。 ）
/*

Author : Slience_K
Belong : C++
Pro : NOIP 2013 - 1 - 3

*/
#include <cstdio>
#include <vector>
#include <algorithm>
#define sz 10005
using namespace std;
struct Node{
int u , v , w;
bool operator < ( const Node & x ) const {
return w > x.w;
}
}data[ 5 * sz ];
const int INF = ( int )( 1e9 );
struct Tyep{
int v , w;
}dot;
vector <Tyep> map[ sz ];
int n , m , q , u , v , f[ sz ] , father[ sz ][ 20 ] , k , power[ 20 ] , w[ sz ][ 20 ] , deep[ sz ];
int Find( int x ){
int t , tt;
t = x;
while( t != f[ t ] ) t = f[ t ];
while( x != f[ x ] ){
tt = f[ x ];
f[ x ] = t;
x = tt;
}
return t;
}
void Dfs( int x , int last , int weight , int d ){
father[ x ][ 0 ] = last;
w[ x ][ 0 ] = weight;
deep[ x ] = d;
for( int i = 0 ; i < map[ x ].size() ; i++ ){
v = map[ x ][ i ].v;
if ( v != last )
Dfs( v , x , map[ x ][ i ].w , d + 1 );
}
}
void Work(){
for( int j = 1 ; j <= k ; j++ )
for( int i = 1 ; i <= n ; i++ ){
v = father[ i ][ j - 1 ];
father[ i ][ j ] = father[ v ][ j - 1 ];
w[ i ][ j ] = min( w[ i ][ j - 1 ] , w[ v ][ j - 1 ] );
}
}
void swap( int &u , int &v ){
int temp = u;
u = v;
v = temp;
}
int LCA( int u , int v ){
int ans = INF;
while( deep[ u ] > deep[ v ] ) swap( u , v );
for( int i = k ; i >= 0 ; i-- )
if ( power[ i ] <= deep[ v ] - deep[ u ] ){
ans = min( w[ v ][ i ] , ans );
v = father[ v ][ i ];
}
for( int i = k ; i >= 0 ; i-- )
if ( father[ v ][ i ] != father[ u ][ i ] ){
ans = min( ans , min( w[ u ][ i ] , w[ v ][ i ] ) );
u = father[ u ][ i ];
v = father[ v ][ i ];
}
if ( u != v ){
ans = min( ans , min( w[ u ][ 0 ] , w[ v ][ 0 ] ) );
}
return ans;
}
int main(){
freopen( "truck.in" , "r" , stdin );
freopen( "truck.out" , "w" , stdout );
scanf( "%d%d" , &n , &m );
power[ 0 ] = 1;
k = 0;
while( power[ k ] <= n ){
power[ k + 1 ] = power[ k ] * 2;
k++;
}
for( int i = 1 ; i <= m ; i++ )
scanf( "%d%d%d" , &data[ i ].u , &data[ i ].v , &data[ i ].w );
sort( data + 1 , data + m + 1 );
for( int i = 1 ; i <= n ; i++ )
f[ i ] = i;
for( int i = 1 ; i <= m ; i++ ){
u = Find( data[ i ].u );
v = Find( data[ i ].v );
if ( v != u ){
f[ v ] = u;
dot.w = data[ i ].w;
dot.v = u;
map[ v ].push_back( dot );
dot.v = v;
map[ u ].push_back( dot );
}
}
for( int i = 1 ; i <= n ; i++ )
if ( father[ i ][ 0 ] == 0 ) Dfs( i , 0 , INF , 1 );

Work();

scanf( "%d" , &q );
for( int i = 1 ; i <= q ; i++ ){
scanf( "%d%d" , &u , &v );
if ( Find( u ) != Find( v ) ) printf( "-1\n" );
else printf( "%d\n" , LCA( u , v ) );
}
fclose( stdin );
fclose( stdout );
return 0;
}

WA那么多次真是太惨了，终于长记性了。判断相不相等不应该是father[x] == father[y]而应该是getfather(x) == getfather(y)
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cctype>
#include <cstring>

using namespace std;

#define INF 1000000000

struct Edge {
int x, y, len;
} edge[50005];

struct Node {
int nextNode, len;
Node *next;
} *N[10005], pool[10000005];

int m, n;
int father[10005];
int cnt;
bool vis[10005];
int depth_node[100005];
int up[10005];
int f0[10005];

int getfather(int x) {
return (father[x] == x) ? x : father[x] = getfather(father[x]);
}
void merge(int x, int y) {
father[getfather(x)] = y;
}
bool cmp(Edge a, Edge b) {
return (a.len > b.len);
}
void mst() {
sort(edge + 1, edge + m + 1, cmp);
for (int i = 1; i <= n; ++i) {
father[i] = i;
}
for (int i = 1; i <= m; ++i) {
//printf("[%d %d %d %d]", edge[i].x, edge[i].y, getfather(edge[i].x), getfather(edge[i].y));
if (getfather(edge[i].x) != getfather(edge[i].y)) {
Node *p = &pool[++cnt];
p->nextNode = edge[i].y;
p->len = edge[i].len;
p->next = N[edge[i].x];
N[edge[i].x] = p;
p = &pool[++cnt];
p->nextNode = edge[i].x;
p->len = edge[i].len;
p->next = N[edge[i].y];
N[edge[i].y] = p;
merge(edge[i].x, edge[i].y);
}
}
}
inline int in() {
int RV = 0;
char p = getchar();
while(!isdigit(p)) {
p = getchar();
}
while(isdigit(p)) {
RV *= 10;
RV += (p - '0');
p = getchar();
}
return RV;
}
void dfs(int k, int depth) {
vis[k] = true;
depth_node[k] = depth;
for (Node *p = N[k]; p; p = p->next) {
if (!vis[p->nextNode]) {
dfs(p->nextNode, depth + 1);
f0[p->nextNode] = k;
up[p->nextNode] = p->len;
}
}
}
int lca(int a, int b) {
int ans = INF;
int d1 = depth_node[a], d2 = depth_node[b];
while (a != b) {
if (d1 > d2) {
ans = min(up[a], ans);
a = f0[a];
--d1;
}
else {
ans = min(up[b], ans);
b = f0[b];
--d2;
}
}
return ans;
}
int main(int argc, const char *argv[]) {
scanf("%d %d", &n, &m);
int x, y, z;
for (int i = 1; i <= m; ++i) {
x = in();
y = in();
z = in();
edge[i].x = x;
edge[i].y = y;
edge[i].len = z;
}
mst();
for (int i = 1; i <= n; ++i)
if (father[i] == i)
dfs(i, 1);
int q = in();
for (int i = 1; i <= q; ++i) {
x = in();
y = in();
if (getfather(x) != getfather(y))
printf("-1\n");
else {
printf("%d\n", lca(x, y));
}
}
return 0;
}

LAC
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define inf 1e8
using namespace std;
struct Tp{
int l,r,w;
}p[50005];
struct Ta{
int x,w;
};
int n,m,q,fa[10005],d[10005][25],f[10005][25],deep[10005];
bool v[10005];
vector<Ta>a[10005];
bool comp(const Tp x,const Tp y)
{
if(x.w>y.w) return true;
return false;
}
int find(int x)
{
if(fa[x]==x) return x;
int y=x,k;
while(x!=fa[x])
x=fa[x];
while(fa[y]!=x)
{
k=fa[y];
fa[y]=x;
y=k;
}
return x;
}
void jia(int k)
{
Ta ta;
int s=p[k].l,t=p[k].r;
ta.w=p[k].w;
ta.x=t;
a[s].push_back(ta);
ta.x=s;
a[t].push_back(ta);
}
void dfs(int u,int de)
{
deep[u]=de;
v[u]=true;
for(int i=0;i<a[u].size();i++)
{
int k=a[u][i].x;
if(!v[k])
{
d[k][0]=a[u][i].w;
f[k][0]=u;
dfs(k,de+1);
}
}
}
void make(int s,int t)
{
int ans=inf,k;
if(deep[s]<deep[t])
swap(s,t);
while(deep[s]>deep[t])
{
ans=min(ans,d[s][0]);
s=f[s][0];
}
while(f[s][0]!=f[t][0])
{
for(k=20;k>=0;k--)
if(f[s][k]!=f[t][k])
break;
ans=min(ans,d[s][k]);
ans=min(ans,d[t][k]);
s=f[s][k];
t=f[t][k];
}
if(s!=t)
{
ans=min(ans,d[s][0]);
ans=min(ans,d[t][0]);
}
printf("%d\n",ans);
}
int main()
{
freopen("truck.in","r",stdin);
freopen("truck.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&p[i].l,&p[i].r,&p[i].w);
sort(p+1,p+m+1,comp);
int k=0,i=0,x,y,fx,fy;
for(int i=1;i<=n;i++)
fa[i]=i;
while(m--)
{
i++;
x=p[i].l,y=p[i].r;
fx=find(x);
fy=find(y);
if(fx!=fy)
{
fa[fx]=fy;
k++;
jia(i);
}
}
memset(v,0,sizeof(v));
for(int i=1;i<=n;i++)
if(!v[i])
dfs(i,1);
////
for(int k=1;k<=20;k++)
for(int i=1;i<=n;i++)
{
d[i][k]=min(d[i][k-1],d[f[i][k-1]][k-1]);
f[i][k]=f[f[i][k-1]][k-1];
}
////////
int s,t;
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
scanf("%d%d",&s,&t);
if(find(s)==find(t))
make(s,t);
else printf("-1\n");
}
fclose(stdin);
fclose(stdout);
return 0;
}

笨的人不用写倍增也能过 跑的不慢

要求最小边最大 跑一遍kruskal 求一个最大生成树
并且要把这棵树建出来 建出来的树可能是森林 所以加一个超级根
然后暴力往上走给定的两个点 一边走一边跟新答案 一直走到lca
如果他们的lca是那个超级根 那么说明不连通 输出-1

有人说要用树上倍增 蒟蒻表示不会 所以想写个暴力看看得多少分
不小心AC了 而且跑的也不慢 真是无语

type
arr=record
long,v,next:longint;
end;
var
t:array[0..20009] of arr;
h,deep,last,fa:array[0..10009] of longint;
bb:array[0..10009] of boolean;
a,b,c:array[0..50009] of longint;
x,y,gen,af,bf,tot,n,m,i:longint;
procedure swap(var a,b:longint);
var ti:longint;
begin
ti:=a; a:=b; b:=ti;
end;
procedure sort(l,r:longint);
var i,j,bi:longint;
begin
i:=l; j:=r; bi:=c[(l+r) div 2];
repeat
while c[i]>bi do inc(i);
while c[j]<bi do dec(j);
if i<=j then
begin
swap(a[i],a[j]); swap(b[i],b[j]); swap(c[i],c[j]);
inc(i); dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;
procedure built(x,y,z:longint);
begin
inc(tot);
t[tot].v:=y;
t[tot].long:=z;
t[tot].next:=last[x];
last[x]:=tot;
end;
function find(x:longint):longint;
begin
if fa[x]=x then exit(x);
fa[x]:=find(fa[x]);
exit(fa[x]);
end;
procedure bfs;
var tou,wei,x,j:longint;
begin
fillchar(bb,sizeof(bb),true);
h[1]:=gen; deep[gen]:=0; bb[gen]:=false;
tou:=0; wei:=1;
while tou<wei do
begin
inc(tou);
j:=last[h[tou]];
while j<>0 do
begin
x:=t[j].v;
if bb[x]=true then
begin
bb[x]:=false;
deep[x]:=deep[h[tou]]+1;
inc(wei); h[wei]:=x;
end;
j:=t[j].next;
end;
end;
end;
function lca(x,y:longint):longint;
var p,ans,j,ti:longint;
begin
ans:=100000000;
if deep[x]>deep[y] then
begin ti:=x; x:=y; y:=ti; end;
while deep[y]>deep[x] do
begin
j:=last[y];
while j<>0 do
begin
p:=t[j].v;
if deep[p]<deep[y] then
begin
y:=p;
if t[j].long<ans then ans:=t[j].long;
end;
j:=t[j].next;
end;
end;
if x=y then exit(ans);
while x<>y do
begin
j:=last[y];
while j<>0 do
begin
p:=t[j].v;
if deep[p]<deep[y] then
begin
y:=p;
if t[j].long<ans then ans:=t[j].long;
end;
j:=t[j].next;
end;
j:=last[x];
while j<>0 do
begin
p:=t[j].v;
if deep[p]<deep[x] then
begin
x:=p;
if t[j].long<ans then ans:=t[j].long;
end;
j:=t[j].next;
end;
end;
if (x=gen) and (y=gen) then exit(-1) else exit(ans);
end;
begin
//assign(input,'1.in'); reset(input);
readln(n,m);
for i:=1 to m do read(a[i],b[i],c[i]);
sort(1,m);
for i:=1 to n do fa[i]:=i;
i:=0; tot:=0;
while i<m do
begin
inc(i);
af:=find(a[i]); bf:=find(b[i]);
if af<>bf then
begin
fa[af]:=bf;
built(a[i],b[i],c[i]);
built(b[i],a[i],c[i]);
end;
end;
gen:=n+1;
fa[gen]:=gen;
for i:=1 to n do
if find(i)<>gen then
begin
fa[find(i)]:=gen;
built(i,gen,0);
built(gen,i,0);
end;
bfs;
read(m);
for i:=1 to m do
begin
read(x,y);
writeln(lca(x,y));
end;
end.

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,fa[10005],f[10005][16],Con[10005][15],d[10005],p;
bool vi[10005];
struct node{
int x,y,z;
bool operator<(const node &tmp)const{
return tmp.z<z;
}
}a[50005];
struct Edge{
int to,dis;
Edge *next;
};
Edge *E[10005],Pr[20005];int cnt;
void addedge(int u,int v,int w){
Pr[++cnt].to=v;Pr[cnt].dis=w;Pr[cnt].next=E[u];E[u]=&Pr[cnt];
Pr[++cnt].to=u;Pr[cnt].dis=w;Pr[cnt].next=E[v];E[v]=&Pr[cnt];
}
int find(int i){
if (fa[i]==i) return i;
return fa[i]=find(fa[i]);
}
void Init(){
scanf("%d%d",&n,&m);
for (int i=0;i<m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
sort(a,a+m);
for (int i=1;i<=n;i++) fa[i]=i;
// for (int i=0;i<m;i++) cout<<a[i].x<<' '<<a[i].z<<endl;
}
void Build(){
for (int i=0;i<m;i++){
int u=find(a[i].x);
int v=find(a[i].y);
if (u!=v){
fa[u]=v;
addedge(a[i].x,a[i].y,a[i].z);
// cout<<a[i].x<<' '<<a[i].y<<' '<<a[i].z<<endl;
}
}
}
void update(int i){
for (int j=1;j<=15&&f[i][j-1]!=-1;j++){
f[i][j]=f[f[i][j-1]][j-1];
// cout<<i<<' '<<j<<endl;
Con[i][j]=min(Con[i][j-1],Con[f[i][j-1]][j-1]);
}
}
void DFS(int u){
// cout<<u<<endl;
update(u);
for (Edge *P=E[u];P;P=P->next){
if (vi[P->to]){
vi[P->to]=false;
d[P->to]=d[u]+1;
f[P->to][0]=u;
Con[P->to][0]=P->dis;
DFS(P->to);
}
}
}
int query(int x,int y){
if (d[x]>d[y])swap(x,y);
int ans1=2147364836;
int ans2=2147364836;
for (int j=15;j>=0;j--)
if (d[f[y][j]]>=d[x]){
ans2=min(ans2,Con[y][j]);
y=f[y][j];
}
if (x==y)return min(ans1,ans2);
for (int j=15;j>=0;j--)
if (f[x][j]!=f[y][j]){
ans1=min(ans1,Con[x][j]);
ans2=min(ans2,Con[y][j]);
x=f[x][j];y=f[y][j];
}
ans1=min(ans1,Con[x][0]);
ans2=min(ans2,Con[y][0]);
return min(ans1,ans2);
}
void Work(){
memset(f,-1,sizeof(f));
memset(vi,true,sizeof(vi));vi[0]=false;
for (int i=1;i<=n;i++) d[i]=-1;
for (int i=1;i<=n;i++){
if (d[i]==-1){
// cout<<i<<endl;
addedge(0,i,-1);
DFS(0);
}
}
/* for (int i=1;i<=n;i++) cout<<d[i]<<' ';cout<<endl;
for (int i=1;i<=n;i++){
for (int j=0;j<=15;j++) cout<<f[i][j]<<' ';
cout<<endl;
}
for (int i=1;i<=n;i++){
for (int j=0;j<=15;j++) cout<<Con[i][j]<<' ';
cout<<endl;
}*/
scanf("%d",&p);
for (int i=0;i<p;i++){
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",query(x,y));
}

}
int main(){
Init();
Build();
Work();
}

Block code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=10010,M=50050;
inline int min(int a,int b) {return a<b?a:b;}
inline int max(int a,int b) {return a>b?a:b;}
inline int read() {
int f=1,x=0; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return f*x;
}
struct Edge{
int to,v,n;
}e[M<<1]; int tot=0,head[N];
bool cmp(const Edge&a,const Edge&b) {return a.n>b.n;}
int n,m,q;
int fa[N][15],D[N][15],len[N];
int f[N];
bool vis[N];
void Init() {
n=read(), m=read();
for(int i=1;i<=n;++i) f[i]=i;
for(int i=1;i<=m;++i)
e[M+i].to=read(),
e[M+i].v=read(),
e[M+i].n=read();
q=read();
sort(e+M+1,e+M+m+1,cmp);
memset(D,0x3f,sizeof(D));
}

int Find(int s) {
return f[s]==s?s:f[s]=Find(f[s]);
}
inline void Add_E(int x,int y,int v) {
e[++tot]=(Edge) {y,v,head[x]}, head[x]=tot;
e[++tot]=(Edge) {x,v,head[y]}, head[y]=tot;
}

void DFS(int s,int l) {
vis[s]=true, len[s]=l;
for(int p=head[s]; p; p=e[p].n) if(!vis[e[p].to]){
int now=e[p].to;
fa[now][0]=s, D[now][0]=e[p].v;
DFS(now,l+1);
}
}
inline void C(int tp,int &x,int &ans) {
for(int k=13;k>=0;--k) {
if(tp<(1<<k)) continue;
ans=min(ans,D[x][k]),
x=fa[x][k];
tp-=(1<<k);
}
}
inline int Ans() {
int x=read(),y=read(),ans=inf;
if(Find(x)!=Find(y)) return -1;
int tp=len[x]-len[y];
if(tp>0) C(tp,x,ans);
else if(tp<0) C(-tp,y,ans);
if(x==y) return ans;
for(int k=13;k>=0;--k) {
if(fa[x][k]==fa[y][k]) continue;
ans=min(min(D[x][k],D[y][k]),ans);
x=fa[x][k], y=fa[y][k];
}
return min(min(D[x][0],D[y][0]),ans);
}
void Solve() {
int pos=M+m,u,v;
for(int i=M+1;i<=pos;++i) {
Find(u=e[i].to),
Find(v=e[i].v);
if(f[u]==f[v]) continue;
f[f[v]]=f[u], Add_E(u,v,e[i].n);
}
for(int i=1;i<=n;++i) if(!vis[i])
DFS(Find(i),0);
for(int k=1;k<=13;++k) {
int nowlen=1<<k;
for(int i=1;i<=n;++i) if(len[i]>=nowlen)
fa[i][k]=fa[fa[i][k-1]][k-1],
D[i][k]=min(D[fa[i][k-1]][k-1],D[i][k-1]);
}
for(int i=0;i<q;++i)
printf("%d\n",Ans());
}
int main() {
//freopen("tmp.txt","r",stdin);
Init();
Solve();
return 0;
}
缩行狂魔...我...

###好吧，其实这道题也不是很难，然而因为种种细节，我错了很多次。
###解法在网上铺天盖地，其实就是克鲁斯卡尔算法加倍增，不用倍增只能得60分；

记录信息
评测状态 Accepted
题目 P1843 货车运输
递交时间 2015-09-27 22:12:12
代码语言 C++
评测机 VijosEx
消耗时间 2284 ms
消耗内存 13948 KiB
评测时间 2015-09-27 22:12:16
评测结果
编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 13948 KiB, score = 5
测试数据 #1: Accepted, time = 0 ms, mem = 13944 KiB, score = 5
测试数据 #2: Accepted, time = 15 ms, mem = 13944 KiB, score = 5
测试数据 #3: Accepted, time = 15 ms, mem = 13944 KiB, score = 5
测试数据 #4: Accepted, time = 15 ms, mem = 13944 KiB, score = 5
测试数据 #5: Accepted, time = 15 ms, mem = 13944 KiB, score = 5
测试数据 #6: Accepted, time = 57 ms, mem = 13944 KiB, score = 5
测试数据 #7: Accepted, time = 46 ms, mem = 13940 KiB, score = 5
测试数据 #8: Accepted, time = 46 ms, mem = 13944 KiB, score = 5
测试数据 #9: Accepted, time = 46 ms, mem = 13940 KiB, score = 5
测试数据 #10: Accepted, time = 46 ms, mem = 13944 KiB, score = 5
测试数据 #11: Accepted, time = 48 ms, mem = 13948 KiB, score = 5
测试数据 #12: Accepted, time = 250 ms, mem = 13948 KiB, score = 5
测试数据 #13: Accepted, time = 250 ms, mem = 13944 KiB, score = 5
测试数据 #14: Accepted, time = 234 ms, mem = 13944 KiB, score = 5
测试数据 #15: Accepted, time = 234 ms, mem = 13944 KiB, score = 5
测试数据 #16: Accepted, time = 250 ms, mem = 13944 KiB, score = 5
测试数据 #17: Accepted, time = 234 ms, mem = 13944 KiB, score = 5
测试数据 #18: Accepted, time = 234 ms, mem = 13940 KiB, score = 5
测试数据 #19: Accepted, time = 234 ms, mem = 13948 KiB, score = 5
Accepted, time = 2284 ms, mem = 13948 KiB, score = 100
代码
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
int f[100010];
struct point{
int u,v,dist;
}edge[100010];
int fa[100010][23];
int best[10010][23];
int dst[100010];
int nxt[100010];
int to[100010];
int fir[100010];
int deep[100010];
int cnt=1;
int n,k;
bool cmp(point a,point b)
{
return a.dist>b.dist;
}
int find(int x){
if(f[x]==x)return x;
else return f[x]=find(f[x]);
}
void add(int a,int b,int dist)
{
nxt[cnt]=fir[a];
to[cnt]=b;
dst[cnt]=dist;
fir[a]=cnt++;
}
void dfs(int now)
{
for(int i=fir[now];i;i=nxt[i])
if(fa[now][0]!=to[i]){
fa[to[i]][0]=now;
best[to[i]][0]=dst[i];
deep[to[i]]=deep[now]+1;
dfs(to[i]);
}
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=k;i++)
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].dist);
sort(edge+1,edge+k+1,cmp);
int x,y;
for(int i=1;i<=k;i++)
if((x=find(edge[i].u))!=(y=find(y=edge[i].v))){
f[x]=y;
add(edge[i].u,edge[i].v,edge[i].dist);
add(edge[i].v,edge[i].u,edge[i].dist);
}
memset(best,127,sizeof(best));
for(int i=1;i<=n;i++)fa[i][0]=i; //这里必须赋初值
dfs(1);
for(int k=1;k<=20;k++)
for(int i=1;i<=n;i++)
{ fa[i][k]=fa[fa[i][k-1]][k-1];
best[i][k]=min(best[i][k-1],best[fa[i][k-1]][k-1]);
}
int Q;
scanf("%d",&Q);
for(int i=1;i<=Q;i++){
int a,b;
scanf("%d%d",&a,&b);
if(find(a)!=find(b)){
printf("-1\n");
continue;
}
if(deep[a]<deep[b]){
swap(a,b);
}
int ans=0x3f3f3f3f;
int d=deep[a]-deep[b];
int x=a,y=b;
for(int k=0;k<=20;k++){

if((d>>k)%2==1){

ans=min(ans,best[x][k]);
x=fa[x][k];
}
}
for(int k=20;x!=y&&k>=0;k--){
if(fa[x][k]!=fa[y][k]||k==0){
ans=min(best[x][k],ans);
ans=min(best[y][k],ans);
x=fa[x][k];
y=fa[y][k];
if(k==0)k++;
}
} //这里要注意，当k=0时，如果循环没退出，必须再找一次k=0，不断循环……
printf("%d\n",ans);
}
}

#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>yu[10000];
int n,m;
int q;
int sum;
int ok[10000];
int d[10000][10000];
void yuxiating(int x,int y,int tot)
{
if(x==y){sum=max(tot,sum);return ;}
for(int i=0;i<yu[x].size();i++)
{

int tot1=min(tot,d[x][yu[x][i]]);
yuxiating(i,y,tot1);
}

}
int main()
{
cin>>n>>m;
int count1=0;
for(int i=0;i<m;i++)
{int x,y,z;
cin>>x>>y>>z;
yu[x].push_back(y);
yu[y].push_back(x);
d[x][y]=z;
d[y][x]=z;
}

cin>>q;

for(int i=0;i<q;i++){
int ii,o;
cin>>ii>>o;
sum=0;

yuxiating(ii,o,10000);

if(sum){
ok[count1++]=sum;}
else{
ok[count1++]=-1;
}

}
for(int i=0;i<count1;i++)
{
cout<<ok[i]<<"\n";
}
return 0;

}

为什么不对