http://www.lydsy.com/JudgeOnline/problem.php?id=3732
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1880 Solved: 894
[Submit][Status][Discuss]
Description
给你N个点的无向图 (1 <= N <= 15,000)，记为：1…N。
图中有M条边 (1 <= M <= 30,000) ，第j条边的长度为： d_j ( 1 < = d_j < = 1,000,000,000).
现在有 K个询问 (1 < = K < = 20,000)。
每个询问的格式是：A B，表示询问从A点走到B点的所有路径中，最长的边最小值是多少？
Input
第一行： N, M, K。
第2..M+1行: 三个正整数：X, Y, and D (1 <= X <=N; 1 <= Y <= N). 表示X与Y之间有一条长度为D的边。
第M+2..M+K+1行: 每行两个整数A B,表示询问从A点走到B点的所有路径中，最长的边最小值是多少？
Output
对每个询问，输出最长的边最小值是多少。
Sample Input
6 6 8
1 2 5
2 3 4
3 4 3
1 4 8
2 5 7
4 6 2
1 2
1 3
1 4
2 3
2 4
5 1
6 2
6 1
1 2 5
2 3 4
3 4 3
1 4 8
2 5 7
4 6 2
1 2
1 3
1 4
2 3
2 4
5 1
6 2
6 1
Sample Output
5
5
5
4
4
7
4
5
5
5
4
4
7
4
5
HINT
1 <= N <= 15,000
1 <= M <= 30,000
1 <= d_j <= 1,000,000,000
1 <= K <= 15,000
Source
最小生成树+倍增
1 #include <algorithm> 2 #include <cstring> 3 #include <cstdio> 4 5 using namespace std; 6 7 const int N(15000+5); 8 const int M(30000+5); 9 int n,m,k; 10 11 #define LL long long 12 int head[N],sumedge; 13 struct E 14 { 15 int u,v,w; 16 }e[M]; 17 bool cmp(E a,E b) 18 { 19 return a.w<b.w; 20 } 21 struct Edge 22 { 23 int v,next; 24 LL dis; 25 Edge(int v=0,int next=0,LL dis=0): 26 v(v),next(next),dis(dis){} 27 }edge[2333333]; 28 inline void ins(int u,int v,LL w) 29 { 30 edge[++sumedge]=Edge(v,head[u],w); 31 head[u]=sumedge; 32 } 33 34 int fa[N],cnt; 35 int find(int x) 36 { 37 return x==fa[x]?x:fa[x]=find(fa[x]); 38 } 39 void Kruskar() 40 { 41 sort(e+1,e+m+1,cmp); 42 for(int i=1;i<=n;i++) fa[i]=i; 43 for(int i=1;i<=m;i++) 44 { 45 int x=e[i].u,y=e[i].v; 46 int fx=find(x),fy=find(y); 47 if(fa[fx]==fy) continue; 48 fa[fx]=fy; 49 ins(x,y,(LL)e[i].w); 50 ins(y,x,(LL)e[i].w); 51 if(++cnt==n-1) return ; 52 } 53 } 54 55 LL maxx[N]; 56 int dad[N],deep[N]; 57 void DFS(int x) 58 { 59 deep[x]=deep[dad[x]]+1; 60 for(int i=head[x];i;i=edge[i].next) 61 { 62 int v=edge[i].v; 63 if(dad[x]==v) continue; 64 maxx[v]=edge[i].dis; 65 dad[v]=x; DFS(v); 66 } 67 } 68 LL LCA(int x,int y) 69 { 70 LL ret=-1; 71 if(deep[x]>deep[y]) swap(x,y); 72 for(;deep[y]>deep[x];y=dad[y]) ret=max(ret,maxx[y]); 73 for(;x!=y;x=dad[x],y=dad[y]) 74 ret=max(ret,max(maxx[x],maxx[y])); 75 return ret; 76 } 77 78 int main() 79 { 80 scanf("%d%d%d",&n,&m,&k); 81 memset(maxx,-1,sizeof(maxx)); 82 for(int u,v,w,i=1;i<=m;i++) 83 scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); 84 Kruskar(); 85 DFS(1); 86 for(int u,v;k--;) 87 { 88 scanf("%d%d",&u,&v); 89 printf("%lld ",LCA(u,v)); 90 } 91 return 0; 92 }