3732: Network
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 2092 Solved: 998
[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
Source
很显然最后的图为一棵最小生成树，然后求一条路径上的最大值即可，一开始想着求最大值用暴力跑一遍，觉得实在是卡不过去，算了吧，这里的最大值可以在LCA的过程中求出，用gg[x][i]表示从第x个点开始到向上(1<<i)个点的路径中的最大值，注意预处理的时候gg[x][i]=max(gg[x][i-1],gg[ fa[x][i-1] ][i-1]); max中第二个gg里面第一维是fa[x][i-1]！！！一开始laj把搞成gg[x][i-1]了 _(:зゝ∠)_ 不过可喜的是交上去的时候一遍过了ovo
1 #include "bits/stdc++.h" 2 using namespace std; 3 typedef long long LL; 4 const int MAX1=15005; 5 const int MAX2=30005; 6 int n,m,K,f[MAX1]; 7 int tot,head[MAX1],adj[MAX2<<1],wei[MAX2<<1],next[MAX2<<1]; 8 int fa[MAX1][21],gg[MAX1][21],deep[MAX1]; 9 struct Edge{10 ????int u,v,w;11 ????bool operator < (const Edge &tt) const {12 ????????return w<tt.w;13 ????}14 }edge[MAX2];15 inline int read(){16 ????int an=0,x=1;char c=getchar();17 ????while (c<‘0‘ || c>‘9‘) {if (c==‘-‘) x=-1;c=getchar();}18 ????while (c>=‘0‘ && c<=‘9‘) {an=(an<<3)+(an<<1)+c-‘0‘;c=getchar();}19 ????return an*x;20 }21 inline int getfather(int x){return f[x]==x?x:f[x]=getfather(f[x]);}22 void addedge(int u,int v,int w){23 ????tot++,adj[tot]=v,wei[tot]=w,next[tot]=head[u],head[u]=tot;24 }25 void dfs(int x,int ff){26 ????int i,j;27 ????for (i=1;i<=20;i++){28 ????????if (deep[x]<(1<<i)) break;29 ????????fa[x][i]=fa[ fa[x][i-1] ][i-1];30 ????????gg[x][i]=max(gg[x][i-1],gg[ fa[x][i-1] ][i-1]);31 ????}32 ????for (i=head[x];i;i=next[i]){33 ????????if (adj[i]!=ff){34 ????????????deep[adj[i]]=deep[x]+1;35 ????????????fa[adj[i]][0]=x;gg[adj[i]][0]=wei[i];36 ????????????dfs(adj[i],x);37 ????????}38 ????}39 }40 int lca(int x,int y){41 ????int an=0,i,j;42 ????if (deep[x]<deep[y]) swap(x,y);43 ????int dd=deep[x]-deep[y];44 ????for (i=20;i>=0;i--)45 ????????if (dd&(1<<i))46 ????????????an=max(an,gg[x][i]),x=fa[x][i];47 ????for (i=20;i>=0;i--){48 ????????if (fa[x][i]!=fa[y][i]){49 ????????????an=max(an,max(gg[x][i],gg[y][i]));50 ????????????x=fa[x][i],y=fa[y][i];51 ????????}52 ????}53 ????if (x!=y) an=max(an,max(gg[x][0],gg[y][0])),x=fa[x][0];54 ????return an;55 }56 int main(){57 ????freopen ("network.in","r",stdin);freopen ("network.out","w",stdout);58 ????int i,j,u,v;tot=1;59 ????n=read();m=read();K=read();60 ????for (i=1;i<=m;i++) edge[i].u=read(),edge[i].v=read(),edge[i].w=read();61 ????sort(edge+1,edge+m+1);62 ????for (i=1;i<=n;i++) f[i]=i;63 ????for (i=1;i<=m;i++){64 ????????int tx=getfather(edge[i].u);65 ????????int ty=getfather(edge[i].v);66 ????????if (tx!=ty){67 ????????????f[tx]=ty;68 ????????????addedge(edge[i].u,edge[i].v,edge[i].w);addedge(edge[i].v,edge[i].u,edge[i].w);69 ????????}70 ????}71 ????dfs(1,0);72 ????for (i=1;i<=K;i++){73 ????????u=read(),v=read();74 ????????printf("%d\n",lca(u,v));75 ????}76 ????return 0;77 }BZOJ-3732: Network (kruskal+LCA)
原文地址：http://www.cnblogs.com/keximeiruguo/p/7725655.html