题目 Sample Input 6 6 8 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 5 4 4 7 4 5
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #define foru(i,a,b) for(int i=a;i<=b;i++) #define m(a,b) memset(a,b,sizeof a) #define en '\n' using namespace std; typedef long long ll; const int N=2e4+5,M=3e4+5,K=18; template<class T>void rd(T &x) { x=0;int f=0;char ch=getchar(); while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x=f?-x:x; return; } struct _Edge{int u,v,w;}e[M]; inline int cmp(_Edge x,_Edge y){ return x.w<y.w; } struct Edge{int to,nex;}edge[N<<1]; int head[N<<1],tot; inline void add(int from,int to){ edge[++tot]=(Edge){to,head[from]};head[from]=tot; } int f[N<<1],val[N],node; inline int seek(int x){ return (x==f[x])?x:(f[x]=seek(f[x])); } int n,m; void ex_kruskal() { foru(i,1,n) f[i]=i; sort(e+1,e+m+1,cmp); int cnt=0;node=n; foru(i,1,m) { int u=e[i].u,v=e[i].v,fu,fv; fu=seek(u),fv=seek(v); if(fu==fv) continue; val[(++node)-n]=e[i].w,++cnt; f[node]=node,f[fu]=node,f[fv]=node; add(node,fu),add(node,fv); if(cnt==(n-1)) break; } } int dep[N<<1],fa[N<<1][K+5];//fa[][]第二维一定是大于K(T_T);这种傻逼错误...犯了好多次,样例会有很多错误... void dfs(int x) { for(int j=1;(1<<j)<=dep[x];j++) fa[x][j]=fa[fa[x][j-1]][j-1]; for(int i=head[x];i;i=edge[i].nex) { int y=edge[i].to; dep[y]=dep[x]+1,fa[y][0]=x; dfs(y); } } int lca(int x,int y) { if(dep[x]<dep[y]) swap(x,y); for(int j=K;j>=0;j--) if(dep[x]-(1<<j)>=dep[y]) x=fa[x][j]; if(x==y) return x; for(int j=K;j>=0;j--) if(fa[x][j]!=fa[y][j]) x=fa[x][j],y=fa[y][j]; return fa[x][0]; } int main() { int q;rd(n),rd(m),rd(q); foru(i,1,m) rd(e[i].u),rd(e[i].v),rd(e[i].w); ex_kruskal(); dep[node]=0,fa[node][0]=node,dfs(node); foru(i,1,q) { int x,y;rd(x),rd(y); printf("%d\n",val[lca(x,y)-n]); } }