题目链接：

题解：

　　一道比较综合的图论题，仍然需要重新构图

　　题目要求“最长边的最小值”，可以让所有路径尽可能短，然后求出路径上最大边即可

　　先求最小生成树，重新构图，再通过求LCA求得路径即可

1 #include
     
        2 #include
      
         3 using namespace std;  4 #define MAXN 15010  5 int n,m,k,heade[MAXN],father[MAXN],fa[17][MAXN],dep[MAXN];  6 struct edge1  7 {  8     int u,v,val;  9 }e1[MAXN*4]; 10 struct edge 11 { 12     int v,next,val; 13 }e[MAXN*4]; 14 int max(int x,int y) 15 { 16     return x>y?x:y; 17 } 18 int find(int x) 19 { 20     return father[x]=father[x]==x?x:find(father[x]); 21 } 22 bool cmp(edge1 a,edge1 b) 23 { 24     return a.val
       
        dep[v])swap(u,v); 45     for(int i=16;~i;i--) 46         if(dep[fa[i][v]]>=dep[u]) 47             v=fa[i][v]; 48     if(u==v)return u; 49     for(int i=16;~i;i--) 50         if(fa[i][u]!=fa[i][v]) 51         { 52             u=fa[i][u]; 53             v=fa[i][v]; 54         } 55     return fa[0][u]; 56 } 57 int main() 58 { 59     scanf("%d%d%d",&n,&m,&k); 60     int x,y,z; 61     for(int i=1;i<=m;i++) 62     { 63         scanf("%d%d%d",&x,&y,&z); 64         adde(i<<1,x,y,z); 65         adde(i<<1+1,y,x,z); 66     } 67     for(int i=1;i<=n;i++) 68         father[i]=i; 69     sort(e1+1,e1+m*2+1,cmp); 70     int cnt=0; 71     for(int i=1;i<=m*2;i++) 72     { 73         x=find(e1[i].u); 74         y=find(e1[i].v); 75         if(x!=y) 76         { 77             int u=e1[i].u,v=e1[i].v; 78             father[y]=x; 79             ++cnt; 80             e[cnt<<1]=(edge){v,heade[u],e1[i].val}; 81             heade[u]=cnt<<1; 82             e[(cnt<<1)+1]=(edge){u,heade[v],e1[i].val}; 83             heade[v]=(cnt<<1)+1; 84             if(cnt==n-1)break; 85         } 86     } 87     //以上为Kruskal  88     dep[1]=fa[0][1]=1; 89     dfs(1); 90     for(int i=1;i<=16;i++) 91         for(int j=1;j<=n;j++) 92             fa[i][j]=fa[i-1][fa[i-1][j]]; 93     while(k--) 94     { 95         scanf("%d%d",&x,&y); 96         int lca=LCA(x,y),t=x,ans=0; 97         while(t!=lca) 98         { 99             for(int i=heade[t];i;i=e[i].next)100             {101                 if(dep[e[i].v]