题意:给你N个点,M条边的无向图 (N<=15000,M<=30000)第j条边的长度为 dj (1<=dj<=1e9),然后K个询问 (1<=K<=20000)。
每个询问的格式是：A B，表示询问从A点走到B点的所有路径中，最长的边最小值是多少？
题解:求所有路径上,那些最大的边中最小的值,也就是“最小”的路径上的最大值，那也是就是最小生成树上,路径的最大值,多次询问,利用树链剖分或者倍增解决
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define lld long long 4 #define N 30005 5 struct rec 6 { 7 int go,next,v; 8 }eg[N],a[N]; 9 int k,m,n,x,y,p,head[N],lca[N][22],q[N][22],dep[N]; 10 int fa[N]; 11 void build(int x,int y,int c) 12 { 13 p++; 14 eg[p].next=head[x]; 15 eg[p].go=y; 16 eg[p].v=c; 17 head[x]=p; 18 } 19 bool cmp(rec x,rec y) 20 { 21 return x.v<y.v; 22 } 23 int get(int x) 24 { 25 if (fa[x]==x) return x; 26 fa[x]=get(fa[x]); 27 return fa[x]; 28 } 29 int query(int x,int y) 30 { 31 int ret=0; 32 if (dep[x]<dep[y]) swap(x,y); 33 for (int i=21;i>=0;i--) 34 if (dep[x]-(1<<i)>=dep[y]) 35 { 36 ret=max(ret,q[x][i]); 37 x=lca[x][i]; 38 } 39 if (x==y) return ret; 40 for (int i=21;i>=0;i--) 41 if (lca[x][i]!=lca[y][i]) 42 { 43 ret=max(ret,max(q[x][i],q[y][i])); 44 x=lca[x][i]; 45 y=lca[y][i]; 46 } 47 ret=max(ret,max(q[x][0],q[y][0])); 48 return ret; 49 } 50 void dfs(int x) 51 { 52 for (int i=head[x];i;i=eg[i].next) 53 { 54 int v=eg[i].go; 55 if (v==lca[x][0]) continue; 56 dep[v]=dep[x]+1; 57 lca[v][0]=x; 58 q[v][0]=eg[i].v; 59 dfs(v); 60 } 61 } 62 int main() 63 { 64 freopen("1.txt","r",stdin); 65 scanf("%d%d%d",&n,&m,&k); 66 for (int i=1;i<=n;i++) fa[i]=i; 67 for (int i=1;i<=m;i++) scanf("%d%d%d",&a[i].go,&a[i].next,&a[i].v); 68 sort(a+1,a+m+1,cmp); 69 int cnt=0; 70 for (int i=1;i<=m;i++) 71 { 72 x=get(a[i].go),y=get(a[i].next); 73 if (x!=y) 74 { 75 fa[x]=y; 76 cnt++; 77 build(a[i].go,a[i].next,a[i].v); 78 build(a[i].next,a[i].go,a[i].v); 79 } 80 if (cnt==n-1) break; 81 } 82 dfs(1); 83 for (int j=1;j<=21;j++) 84 for (int i=1;i<=n;i++) 85 if (lca[i][j-1]) 86 { 87 lca[i][j]=lca[lca[i][j-1]][j-1]; 88 q[i][j]=max(q[i][j-1],q[lca[i][j-1]][j-1]); 89 } 90 while (k--) 91 { 92 scanf("%d%d",&x,&y); 93 printf("%d ",query(x,y)); 94 } 95 }