3732: Network
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 2392 Solved: 1135
[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
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
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
昨天翻Mybing博客的时候发现了 http://www.cnblogs.com/mybing/p/8610357.html#3928587
这道题很裸的做法就是跑一下kruskal，对于每次询问输出x到lca(x,y)，以及y到lca(x,y)中间的最大值即可
还有一种就是kruskal重构树，但是貌似拿来做这道题的话有点大材小用了 不过拿来练板子还是可以的
具体什么是kruskal重构树 https://blog.csdn.net/wu_tongtong/article/details/77601523
kruskal有一些很优秀的性质，比如说这棵树是一个大根堆，有二叉性质...
等到以后用到这行性质再说吧
#include <bits/stdc++.h>#define ll long long#define inf 1e9+10using namespace std;inline int read(){int x=0;int f=1;char ch=getchar();while(!isdigit(ch)) {if(ch==‘-‘) f=-1;ch=getchar();}while(isdigit(ch)) {x=x*10+ch-‘0‘;ch=getchar();}return x*f;}const int MAXN=1e5+10;struct node{int y,next;}e[MAXN];int linkk[MAXN],len=0,f[MAXN][30],dep[MAXN],n,m,fa[MAXN],v[MAXN],p;struct edge{int x,y,v;}d[MAXN];inline void insert(int x,int y){e[++len].y=y;e[len].next=linkk[x];linkk[x]=len;}inline bool cmp(edge n,edge m){return n.v<m.v;}inline int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]); }void kruskal(){for(int i=1;i<=n;i++) fa[i]=i;p=n;sort(d+1,d+m+1,cmp);for(int i=1;i<=m;i++){int x=getfa(d[i].x);int y=getfa(d[i].y);if(x!=y){p++;fa[x]=p;fa[y]=p;v[p]=d[i].v;fa[p]=p;insert(p,x);insert(p,y);}}}inline void getdep(int x,int fa){f[x][0]=fa;for(int i=linkk[x];i;i=e[i].next){dep[e[i].y]=dep[x]+1;getdep(e[i].y,x);}}void getanser(){for(int i=1;i<=24;i++){for(int j=1;j<=p;j++){f[j][i]=f[f[j][i-1]][i-1];}}}inline int getlca(int x,int y){if(x==y) return x;if(dep[x]<dep[y]) swap(x,y);for(int i=24;i>=0;i--){if(dep[x]-(1<<i)>=dep[y]){x=f[x][i];}}if(x==y) return x;for(int i=24;i>=0;i--){if(f[x][i]!=f[y][i]&&f[x][i]){x=f[x][i];y=f[y][i];}}return f[x][0];}int main(){n=read();m=read();int t=read();for(int i=1;i<=m;i++){d[i].x=read();d[i].y=read();d[i].v=read();}kruskal();dep[p]=1;getdep(p,0);getanser();for(int i=1;i<=t;i++){int x=read();int y=read();printf("%d\n",v[getlca(x,y)]);}return 0;}
BZOJ 3732 Network
原文地址：https://www.cnblogs.com/something-for-nothing/p/9069552.html