[原创]2017年第0届浙江工业大学之江学院程序设计竞赛决赛 H: qwb与学姐 [MST+LCA]【数据结构】

# include<bits/stdc++.h>
typedef long long int LL;
using namespace std;
 
const int N = 50000+7;
const int MOD = 1e9+7;
const int INF = (~(1<<31));
const double Pi = acos(-1.0);
 
int read(){
    int x=0,f=1;char ch= getchar();
    while('0'>ch||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
/*****************************/
int n,m,k;
vector<pair<int,int> >G[N];
void add(int u,int v,int w){
    G[u].push_back(make_pair(v,w));
    G[v].push_back(make_pair(u,w));
}
struct node {
    int u,v,w;
}e[N*4];
bool cmp(node a,node b){
    return a.w>b.w;
}
/*****************************/
int pre[N];
int findi(int x){
    int r=x;
    while(r!=pre[r])r=pre[r];
    int i=x,j;
    while(i!=r){
        j=pre[i];
        pre[i]=r;
        i=j;
    }
    return r;
}
void join(int x,int y){
    int fx=findi(x),fy=findi(y);
    pre[fx]=fy;
}
void MST(){
    for(int i=1,sum=0;i<=m&&sum<n-1;i++){
        if(findi(e[i].u)==findi(e[i].v)) continue;
        join(e[i].u,e[i].v);
        add(e[i].u,e[i].v,e[i].w);
        sum++;
    }
}
/*****************************/
int fa[N][20],dep[N],mi[N][20];
void dfs(int u,int f,int d){
    fa[u][0]=f;dep[u]=d;
    for(int i=1;i<20;i++)
        fa[u][i]=fa[fa[u][i-1]][i-1],mi[u][i]=min(mi[u][i-1],mi[fa[u][i-1]][i-1]);
    int gz=G[u].size();
    for(int i=0,to;i<gz;i++){
        to=G[u][i].first;
        if(to==f)continue;
        mi[to][0]=G[u][i].second;
        dfs(to,u,d+1);
    }
}
void solve(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    int lca=-1,tu=u,tv=v;
 
    for(int i=19;i>=0;i--)
        if(dep[fa[u][i]]>=dep[v])
            u=fa[u][i];
 
    if(u==v) lca=v;// return v;
    else{
        for(int i=19;i>=0;i--){
            if(fa[u][i]==fa[v][i]) continue;
            u=fa[u][i];
            v=fa[v][i];
        }
        lca = fa[v][0];//return fa[v][0];
    }
//    cout<<lca<<"  ";
    int miu=INF,miv=INF;
    for(int i=19;i>=0;i--){
        if(dep[fa[tu][i]]>=dep[lca])
            miu=min(miu,mi[tu][i]),tu=fa[tu][i];
        if(dep[fa[tv][i]]>=dep[lca])
            miv=min(miv,mi[tv][i]),tv=fa[tv][i];
    }
    //miu=min(miu,mi[tu][0]),miv=min(miv,mi[tv][0]);
    printf("%d\n",min(miu,miv));
}
/*****************************/
void init(){
    for(int i=1;i<=n;i++) pre[i]=i;
    memset(mi,0x7f,sizeof(mi));
}
 
int main(){
    while(~scanf("%d%d%d",&n,&m,&k)){
        init();
        for(int i=1;i<=m;i++)    scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
        sort(e+1,e+m+1,cmp);
        MST();
        dfs(1,0,1);
//        for(int i=1;i<=n;i++){
//            printf("%d: ",i);
//            for(int j=0;j<20;j++)
//                printf("%d ",mi[i][j]);
//            puts("");
//        }
        for(int u,v;k--;){
            scanf("%d%d",&u,&v);
            solve(u,v);
        }
    }
    return 0;
}