[数据结构与算法]洛谷P1967 [NOIP2013 提高组] 货车运输（最大生成树+LCA）

题目
思路
由题可知，我们要求的是最大载重，而且这个最大载重要适用于每条边，所以毫无疑问这是个求最小的最大问题。这时候我们应该构建最大生成树。得到了这样一个树之后，我们便考虑如何求出两个节点之间最小边权的最大值（即为题中的最大载重），因为这两点之间的路径是唯一的，我们只需要找出这条路径便可以得到答案，a，b两点有且只有一条路径连通，我们可以通过LCA将a，b两点连的路都走一遍，并且每经过每条路都对限重进行比较，以保证求得最大限重。
代码如下

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+5;
const int inf=0x3f3f3f3f;
typedef long long ll;
int n,m;
struct Edge
{
    int from,to,dist;
}Edges[maxn];
int cnt=0;
int f[maxn];
vector<Edge>edges;
vector<int>G[maxn];
void add(int from,int to,int dist)
{
    edges.push_back({from,to,dist});
    int m=edges.size();
    G[from].push_back(m-1);
}

bool cmp(Edge a,Edge b)
{
    return a.dist>b.dist;
}

int find(int x)
{
    return f[x]==x?x:f[x]=find(f[x]);
}

void kruskal()
{
    sort(Edges+1,Edges+1+cnt,cmp);
    for(int i=1;i<=n;i++)
        f[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x=find(Edges[i].from),y=find(Edges[i].to);
        if(x!=y)
        {
           // cout<<Edges[i].dist<<endl;
            f[x]=y;
            add(Edges[i].from,Edges[i].to,Edges[i].dist);
            add(Edges[i].to,Edges[i].from,Edges[i].dist);
        }
    }
}

int F[maxn][21],W[maxn][21],deep[maxn];
bool vis[maxn];

void dfs(int u,int fa,int d)
{
    vis[u]=true;
    deep[u]=deep[fa]+1;
    F[u][0]=fa;
    W[u][0]=d;
    for(int i=1;(1<<i)<=deep[u];i++)
    {
        F[u][i]=F[F[u][i-1]][i-1];
        W[u][i]=min(W[u][i-1],W[F[u][i-1]][i-1]);
    }
    for(int i=0;i<G[u].size();i++)
    {
        Edge e=edges[G[u][i]];
        int v=e.to;
        if(vis[v])
            continue;
        dfs(v,u,e.dist);
    }
}

int LCA(int x,int y)
{
    if(find(x)!=find(y))
        return -1;
    int ans=inf;
    if(deep[x]>deep[y])
        swap(x,y);
    for(int i=20;i>=0;i--)
    {
        if(deep[F[y][i]]>=deep[x])
        {
            ans=min(ans,W[y][i]);//注意一定要先更新答案，再更新位置！！
             y=F[y][i];
        }

    }
    if(x==y)
        return ans;
    for(int i=20;i>=0;i--)
    {
        if(F[x][i]!=F[y][i])
        {
            ans=min(ans,min(W[x][i],W[y][i]));//注意一定要更新答案，再更新位置！！
            x=F[x][i];
            y=F[y][i];

        }
    }
    ans=min(ans,min(W[x][0],W[y][0]));  //更新此时x,y到公共祖先最大载重，fa[x][0], fa[y][0]即为公共祖先 
    return ans;
}

int main()
{

    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        Edges[++cnt].from=x;
        Edges[cnt].to=y;
        Edges[cnt].dist=z;
    }
    kruskal();
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            deep[i]=0;
            dfs(i,i,inf);
            F[i][0]=i;
            W[i][0]=inf;
        }
    }
    int q;
    cin>>q;
    for(int i=0;i<q;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        cout<<LCA(x,y)<<endl;
    }
}