[NOIp 2013]货车运输

Description

A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

Input

输入文件名为 truck.in。

输入文件第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道

路。 接下来 m 行每行 3 个整数 x、 y、 z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意： x 不等于 y，两座城市之间可能有多条道路 。

接下来一行有一个整数 q，表示有 q 辆货车需要运货。

接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意： x 不等于 y 。

Output

输出文件名为 truck.out。

输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货

车不能到达目的地，输出-1。

Sample Input

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

Sample Output

3
-1
3

Hint

对于 30%的数据，0 < n < 1,000，0 < m < 10,000，0 < q< 1,000；

对于 60%的数据，0 < n < 1,000，0 < m < 50,000，0 < q< 1,000；

对于 100%的数据，0 < n < 10,000，0 < m < 50,000，0 < q< 30,000，0 ≤ z ≤ 100,000。

题解

$Kruskal$+$LCA$+并查集
    建最大生成森林（以保证联通性的情况下最大化瓶颈路径）。
    并查集判断是否联通。
    若联通，$LCA$出路径上的最短边。

 #include<map>
 #include<ctime>
 #include<cmath>
 #include<queue>
 #include<stack>
 #include<cstdio>
 #include<string>
 #include<vector>
 #include<cstring>
 #include<cstdlib>
 #include<iostream>
 #include<algorithm>
 #define LL long long
 #define RE register
 #define IL inline
 using namespace std;
 const int N=;
 const int M=;

 IL int Min(const int &a,const int &b) {return a<b ? a:b;}

 int n,m,q,lim,x,y;
 struct tt
 {
     int from,to,cost;
 }lin[M+];
 IL bool comp(const tt &a,const tt &b) {return a.cost>b.cost;}

 int set[N+];
 IL int Find(int r) {return set[r] ? set[r]=Find(set[r]):r;}
 IL void Kruskal();

 struct ss
 {
     int to,next,cost;
 }edge[N*+];
 int path[N+],top;
 IL void Add(int u,int v,int c);

 bool vis[N+];
 int fa[N+][],minn[N+][],dep[N+];
 void Dfs(int r,int depth);
 IL void RMQ();

 IL int LCA(int x,int y);

 int main()
 {
     scanf("%d%d",&n,&m);lim=log2(n);
     for (RE int i=;i<=m;i++) scanf("%d%d%d",&lin[i].from,&lin[i].to,&lin[i].cost);
     Kruskal();
     for (RE int i=;i<=n;i++) if (!vis[i]) Dfs(i,);
     RMQ();
     scanf("%d",&q);
     while (q--)
     {
         scanf("%d%d",&x,&y);
         int a=Find(x);
         int b=Find(y);
         if (a!=b) printf("-1\n");
         else printf("%d\n",LCA(x,y));
     }
     return ;
 }

 IL void Kruskal()
 {
     sort(lin+,lin+m+,comp);
     int cnt=;
     for (RE int i=;i<=m;i++)
     {
         int q=Find(lin[i].from);
         int p=Find(lin[i].to);
         if (p!=q)
         {
             set[p]=q;
             cnt++;
             Add(lin[i].from,lin[i].to,lin[i].cost);
             Add(lin[i].to,lin[i].from,lin[i].cost);
             if (cnt==n-) break;
         }
     }
 }
 IL void Add(int u,int v,int c)
 {
     edge[++top].to=v;
     edge[top].next=path[u];
     edge[top].cost=c;
     path[u]=top;
 }
 void Dfs(int r,int depth)
 {
     vis[r]=;
     dep[r]=depth;
     for (RE int i=path[r];i;i=edge[i].next) if (!vis[edge[i].to])
     {
         fa[edge[i].to][]=r;
         minn[edge[i].to][]=edge[i].cost;
         Dfs(edge[i].to,depth+);
     }
 }
 IL void RMQ()
 {
     for (RE int t=;t<=lim;t++)
         for (RE int i=;i<=n;i++)
         {
             fa[i][t]=fa[fa[i][t-]][t-];
             minn[i][t]=Min(minn[i][t-],minn[fa[i][t-]][t-]);
         }
 }
 IL int LCA(int x,int y)
 {
     int ans=2e9;
     if (dep[x]<dep[y]) swap(x,y);
     for (RE int i=lim;i>=;i--) if (dep[x]-(<<i)>=dep[y])
     {
         ans=Min(ans,minn[x][i]);
         x=fa[x][i];
     }
     if (x!=y)
     {
         for (RE int i=lim;i>=;i--) if (fa[x][i]!=fa[y][i])
         {
             ans=Min(ans,minn[x][i]);
             ans=Min(ans,minn[y][i]);
             x=fa[x][i];
             y=fa[y][i];
         }
         ans=Min(ans,minn[x][]);
         ans=Min(ans,minn[y][]);
         x=fa[x][];
         y=fa[y][];
     }
     return ans;
 }