火車運輸（NOIP2013）

傳送藥水

（喝了這一壺傳送藥水，保你看了什麼題都覺得神清氣爽）

這題不算水。

首先想到，肯定需要跑一遍最大生成樹，因為我們需要盡可能大的限制。

那麼，接下來就是求兩點之間最小限制。

那麼就是我們就可以用求LCA（最近公共祖先）來解決這個問題。

是以就倍增好了。

我們這裡倍增的有兩個數組，一個是祖先，另一個是目前點到祖先的路上的最小限制。

最後理一遍思路：

先kruskal建立一個最大樹（圖）。

然後bfs建立一個樹，處理一些基本資料。

然後就用倍增求LCA來解決就好了。

代碼如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
struct edge{
    int u,v,w;
};
int n,m;
int p[];
edge e[];
int f[][],deep[];
int g[][];
int vis[];
vector<int> G[],H[];
//int fa[10005];
int ques;
int find(int xx){
    return xx==p[xx]?xx:p[xx]=find(p[xx]);
}
int cmp(edge a,edge b){
    return a.w>b.w;
}
void kruscal(){
    sort(e,e+m,cmp);
    for(int i=;i<=n;i++){
        p[i]=i;
    }
    for(int i=;i<m;i++){
        int xx=find(e[i].u),yy=find(e[i].v);
        if(xx!=yy){
            p[xx]=yy;
            G[e[i].u].push_back(e[i].v);
            G[e[i].v].push_back(e[i].u);
            H[e[i].u].push_back(e[i].w);
            H[e[i].v].push_back(e[i].w);

        }
    }
}
void bfs(){
    memset(g,,sizeof(g));
    memset(vis,,sizeof(vis));
    memset(f,-,sizeof(f));
    queue<int> q;
    int cur=;
    deep[cur]=;
    q.push(cur);
    vis[cur]=;
//  f[cur][0]=-1;
//  fa[cur]=-1;
    while(!q.empty()){
        cur=q.front();
        q.pop(); 
        int len=G[cur].size();
        for(int i=;i<len;i++){
            if(vis[G[cur][i]]==){
                q.push(G[cur][i]);
                vis[G[cur][i]]=;
                deep[G[cur][i]]=deep[cur]+;
                f[G[cur][i]][]=cur;
//              fa[G[cur][i]]=cur;//待定 
                g[G[cur][i]][]=H[cur][i];
            }
        }
    }
}
void init(){
    for(int k=;k<;k++){
        for(int j=;j<=n;j++){
            if(f[j][k]!=-){
                f[j][k+]=f[f[j][k]][k];
                g[j][k+]=min(g[j][k],g[f[j][k]][k]);
            }
        }
    }
}
int ans;
int jump(int u,int step){
    for(int k=;k<;k++){
        if(step&(<<k)){
            ans=min(ans,g[u][k]);
            u=f[u][k];

        }
    }
    return u;
}
void lca(int u,int v){
    ans=;
    if(deep[u]<deep[v]){
        swap(u,v);
    }
    u=jump(u,deep[u]-deep[v]);
    for(int k=;k>=;k--){
        if(f[u][k]!=f[v][k]){
            ans=min(min(ans,g[u][k]),g[v][k]);
            u=f[u][k];
            v=f[v][k];
        }
    }
    ans=u==v?ans:min(min(ans,g[u][]),g[v][]);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=;i<m;i++){
        e[i].w=;
    }
    for(int i=;i<m;i++){
        int ww;
        scanf("%d%d%d",&e[i].u,&e[i].v,&ww);
        e[i].w=max(e[i].w,ww);
    }
    kruscal();
    bfs();
    init();
    scanf("%d",&ques);
    while(ques--){
        int u,v;
        scanf("%d%d",&u,&v);
        if(u>n||v>n){
            printf("-1\n");
            continue;
        }
        if(find(u)!=find(v)){
            printf("-1\n");
            continue;
        }else{
            lca(u,v);
            if(ans<){
                printf("%d\n",ans);
            }else{
                printf("-1\n");
            }
        }
    }
    return ;
}