Problem H: qwb与学姐 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 176 Solved: 61 [Submit][Status][Web Board] Description qwb打算向学姐表白，可是学姐已经受够了他的骚扰，于是出了一个题想难住他: 已知一幅n个点m条边的无向图,定义路径的值为这条路径上最短的边的长度， 现在有 k个询问， 询问从A点到B点的所有路径的值的最大值。 qwb听完这个问题很绝望啊,聪明的你能帮帮他吗? Input 一组数据。 第一行三个整数n，m，k (1<=N<=50000,m<=200000,k<=100000)。 第2..m+1行：三个正整数：X, Y, and D (1 <= X <=N; 1 <= Y <= N,1<=D<=215) 表示X与Y之间有一条长度为D的边。 第m+2..m+k+1行： 每行两个整数A B(1<=A,B<=n且A≠B)，意义如题目描述。 保证图连通。 Output 对于每个询问输出一行，一共k行，每行输出A点到B点的所有路径的值的最大值。 Sample Input 4 5 3 1 2 6 1 3 8 2 3 4 2 4 5 3 4 7 2 3 1 4 3 4 Sample Output 6 7 7 题解：首先先建一棵最大生成树，则这个答案为u到v路上的最小值。 树链剖分后（因为是边权，所以将边权赋给远离根节点的点），求出lca，则答案就在（tree[u],tree[lca]+1)(tree[v],tree[lca]+1)之中。好像用树链剖分求lca太浪费了，加了个读入外挂才勉勉强强过（980ms）。 代码：
#include<bits/stdc++.h> typedef long long int ll; using namespace std; const int N=200010; int read(){ int x=0;char ch = getchar(); while('0'>ch||ch>'9')ch=getchar(); while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x; } int n,m,k,cnt,tot; int dep[N],fa[N],siz[N],son[N]; int f[N]; int sum[N<<2]; int u,v; struct node { int u,v,w; bool operator <(const node &t)const { return w>t.w; } }a[N]; int head[N<<2]; int b[N]; struct nod { int to,next,w; }edge[N<<2]; int find(int x) { return x==f[x]?x:f[x]=find(f[x]); } void join(int x,int y) { int xx=find(x); int yy=find(y); if(xx!=yy) f[xx]=yy; } void add(int u,int v,int w) { edge[cnt].to=v,edge[cnt].next=head[u],edge[cnt].w=w,head[u]=cnt++; edge[cnt].to=u,edge[cnt].next=head[v],edge[cnt].w=w,head[v]=cnt++; } void mst() { for(int i=1,su=0;i<=m&&su<n-1;i++) { if(find(a[i].u)==find(a[i].v)) continue; join(a[i].u,a[i].v); add(a[i].u,a[i].v,a[i].w); su++; } } void dfs1(int u,int f,int d) { dep[u]=d,fa[u]=f,siz[u]=1,son[u]=0; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(v==f)continue; b[v]=edge[i].w; dfs1(v,u,d+1); siz[u]+=siz[v]; if(siz[son[u]]<siz[v]) son[u]=v; } } int top[N],pre[N],tree[N]; void dfs2(int u,int tp) { top[u]=tp,tree[u]=++tot,pre[tree[u]]=u; if(!son[u]) return ; dfs2(son[u],tp); for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(v==fa[u]||v==son[u]) continue; dfs2(v,v); } } int lca(int x,int y) { int fx=top[x],fy=top[y]; while(fx!=fy) { if(dep[fx]<dep[fy]) swap(x,y),swap(fx,fy); x=fa[fx],fx=top[x]; } if(dep[x]>dep[y])swap(x,y); return x; } void init() { cnt=0; tot=0; memset(head,-1,sizeof(head)); memset(sum,0,sizeof(sum)); for(int i=1;i<=n;i++) f[i]=i; } void pushup(int rt) { sum[rt]=min(sum[rt<<1],sum[rt<<1|1]); } void build(int l,int r,int rt) { if(l==r) { sum[rt]=b[pre[l]]; return ; } int mid=(r+l)>>1; build(l,mid,rt<<1); build(mid+1,r,rt<<1|1); pushup(rt); } int query_min(int l,int r,int ll,int rr,int rt) { if(ll<=l&&rr>=r) { return sum[rt]; } int ans=1e7; int mid=(r+l)>>1; if(ll<=mid) ans=min(ans,query_min(l,mid,ll,rr,rt<<1)); if(rr>mid) ans=min(ans,query_min(mid+1,r,ll,rr,rt<<1|1)); return ans; } int find_min(int x,int y) { int ans=1e7; int fx=top[x],fy=top[y]; while(fx!=fy) { if(dep[fx]<dep[fy]) swap(x,y),swap(fx,fy); ans=min(ans,query_min(1,n,tree[fx],tree[x],1)); x=fa[fx],fx=top[x]; } if(dep[x]>dep[y]) swap(x,y); ans=min(ans,query_min(1,n,tree[x]+1,tree[y],1)); return ans; } int main() { n=read(),m=read(),k=read(); init(); for(int i=1;i<=m;i++) { a[i].u=read(); a[i].v=read(); a[i].w=read(); } sort(a+1,a+1+m); mst(); dfs1(1,0,1); dfs2(1,1); b[1]=1e8; build(1,n,1); while(k--) { u=read(); v=read(); int lc=lca(u,v); int lmin=find_min(u,lc); int rmin=find_min(v,lc); printf("%d\n",min(lmin,rmin)); } }