本文主要是介绍BZOJ 3732 Network Kruskal+倍增，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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
传送门
和货车运输完全一样……
就是这题求的是最大边最小而已，那就最小生成树+倍增最大值。
还有数据范围也有一丢丢不一样。。所以贴题要小心
#include<bits/stdc++.h>
using namespace std;
const intN=15005,M=30005;
int n,m,Ecnt;
int dep[N],FA[N],faa[N];
int fa[N][15],st[N][15];
bool vis[N];
int getFA(int x){if (FA[x]!=x) FA[x]=getFA(FA[x]);return FA[x];
}
int getfaa(int x){if (faa[x]!=x) faa[x]=getfaa(faa[x]);return faa[x];
}
struct Edge1{int l,r,val;}E1[M<<1];
bool cmp(Edge1 x,Edge1 y){return x.val<y.val;}
struct Edge2{int next,to,val;
}E[N<<1];int head[N];
void add(int u,int v,int w){E[++Ecnt].next=head[u];E[Ecnt].to=v;E[Ecnt].val=w;head[u]=Ecnt;
}
void Pre(){for (int j=1;j<=14;j++)for (int i=1;i<=n;i++)if (fa[i][j-1]){fa[i][j]=fa[fa[i][j-1]][j-1];st[i][j]=max(st[i][j-1],st[fa[i][j-1]][j-1]);}
}
void dfs(int u,int pre,int depth){vis[u]=1;fa[u][0]=pre,dep[u]=depth;for (int i=head[u];i;i=E[i].next){int v=E[i].to;if (v==pre) continue;st[v][0]=E[i].val;dfs(v,u,depth+1);}
}
int ANS(int u,int v){if (dep[u]<dep[v]) swap(u,v);int t=dep[u]-dep[v],tt=0;for (int i=0;i<=14;i++)if ((1<<i)&t) tt=max(tt,st[u][i]),u=fa[u][i];if (u==v) return tt;for (int i=14;i>=0;i--)if (fa[u][i]!=fa[v][i]){if (u!=v) tt=max(tt,max(st[u][i],st[v][i]));u=fa[u][i],v=fa[v][i];}tt=max(tt,max(st[u][0],st[v][0]));return tt;
}
int main(){int Q;scanf("%d%d%d",&n,&m,&Q);for (int i=1;i<=m;i++)scanf("%d%d%d",&E1[i].l,&E1[i].r,&E1[i].val);sort(E1+1,E1+1+m,cmp);for (int i=1;i<=n;i++) FA[i]=faa[i]=i;for (int i=1;i<=m;i++){int t1=getFA(E1[i].l),t2=getFA(E1[i].r);if (t1==t2) continue;FA[t2]=t1;add(E1[i].l,E1[i].r,E1[i].val),add(E1[i].r,E1[i].l,E1[i].val);t1=getfaa(E1[i].l),t2=getfaa(E1[i].r);if (t1!=t2) faa[t2]=t1;}for (int i=1;i<=n;i++)if (!vis[i]) dfs(i,0,0);Pre();int x,y;while (Q--){scanf("%d%d",&x,&y);if (getfaa(x)!=getfaa(y)) puts("-1");else printf("%d\n",ANS(x,y));}return 0;
}
这篇关于BZOJ 3732 Network Kruskal+倍增的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
