[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

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$出路径上的最短边。

  1 #include<map>
  2 #include<ctime>
  3 #include<cmath>
  4 #include<queue>
  5 #include<stack>
  6 #include<cstdio>
  7 #include<string>
  8 #include<vector>
  9 #include<cstring>
 10 #include<cstdlib>
 11 #include<iostream>
 12 #include<algorithm>
 13 #define LL long long
 14 #define RE register
 15 #define IL inline
 16 using namespace std;
 17 const int N=10000;
 18 const int M=50000;
 19 
 20 IL int Min(const int &a,const int &b) {return a<b ? a:b;}
 21 
 22 int n,m,q,lim,x,y;
 23 struct tt
 24 {
 25     int from,to,cost;
 26 }lin[M+5];
 27 IL bool comp(const tt &a,const tt &b) {return a.cost>b.cost;}
 28 
 29 int set[N+5];
 30 IL int Find(int r) {return set[r] ? set[r]=Find(set[r]):r;}
 31 IL void Kruskal();
 32 
 33 struct ss
 34 {
 35     int to,next,cost;
 36 }edge[N*2+5];
 37 int path[N+5],top;
 38 IL void Add(int u,int v,int c);
 39 
 40 bool vis[N+5];
 41 int fa[N+5][15],minn[N+5][15],dep[N+5];
 42 void Dfs(int r,int depth);
 43 IL void RMQ();
 44 
 45 IL int LCA(int x,int y);
 46 
 47 int main()
 48 {
 49     scanf("%d%d",&n,&m);lim=log2(n);
 50     for (RE int i=1;i<=m;i++) scanf("%d%d%d",&lin[i].from,&lin[i].to,&lin[i].cost);
 51     Kruskal();
 52     for (RE int i=1;i<=n;i++) if (!vis[i]) Dfs(i,1);
 53     RMQ();
 54     scanf("%d",&q);
 55     while (q--)
 56     {
 57         scanf("%d%d",&x,&y);
 58         int a=Find(x);
 59         int b=Find(y);
 60         if (a!=b) printf("-1
");
 61         else printf("%d
",LCA(x,y));
 62     }
 63     return 0;
 64 }
 65 
 66 IL void Kruskal()
 67 {
 68     sort(lin+1,lin+m+1,comp);
 69     int cnt=0;
 70     for (RE int i=1;i<=m;i++)
 71     {
 72         int q=Find(lin[i].from);
 73         int p=Find(lin[i].to);
 74         if (p!=q)
 75         {
 76             set[p]=q;
 77             cnt++;
 78             Add(lin[i].from,lin[i].to,lin[i].cost);
 79             Add(lin[i].to,lin[i].from,lin[i].cost);
 80             if (cnt==n-1) break;
 81         }
 82     }
 83 }
 84 IL void Add(int u,int v,int c)
 85 {
 86     edge[++top].to=v;
 87     edge[top].next=path[u];
 88     edge[top].cost=c;
 89     path[u]=top;
 90 }
 91 void Dfs(int r,int depth)
 92 {
 93     vis[r]=1;
 94     dep[r]=depth;
 95     for (RE int i=path[r];i;i=edge[i].next) if (!vis[edge[i].to])
 96     {
 97         fa[edge[i].to][0]=r;
 98         minn[edge[i].to][0]=edge[i].cost;
 99         Dfs(edge[i].to,depth+1);
100     }
101 }
102 IL void RMQ()
103 {
104     for (RE int t=1;t<=lim;t++)
105         for (RE int i=1;i<=n;i++)
106         {
107             fa[i][t]=fa[fa[i][t-1]][t-1];
108             minn[i][t]=Min(minn[i][t-1],minn[fa[i][t-1]][t-1]);
109         }
110 }
111 IL int LCA(int x,int y)
112 {
113     int ans=2e9;
114     if (dep[x]<dep[y]) swap(x,y);
115     for (RE int i=lim;i>=0;i--) if (dep[x]-(1<<i)>=dep[y])
116     {
117         ans=Min(ans,minn[x][i]);
118         x=fa[x][i];
119     }
120     if (x!=y)
121     {
122         for (RE int i=lim;i>=0;i--) if (fa[x][i]!=fa[y][i])
123         {
124             ans=Min(ans,minn[x][i]);
125             ans=Min(ans,minn[y][i]);
126             x=fa[x][i];
127             y=fa[y][i];
128         }
129         ans=Min(ans,minn[x][0]);
130         ans=Min(ans,minn[y][0]);
131         x=fa[x][0];
132         y=fa[y][0];
133     }
134     return ans;
135 }