题目:https://www.luogu.org/problemnew/show/P1967
就是倍增LCA的裸题,注意一些细节即可。
代码如下:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int const MAXN=10005,MAXM=50005,inf=1e9; int n,m,q,dep[MAXN],pre[MAXN][20],mn[MAXN][20],ct1,ct=1,head[MAXN]; int fa[MAXN],ans; struct N{ int hd,to,next,w; N(int h=0,int t=0,int n=0,int w=0):hd(h),to(t),next(n),w(w) {} }edge[MAXM<<1],ed[MAXM<<1]; int find(int x) { if(x==fa[x])return x; return fa[x]=find(fa[x]); } void add(int x,int y,int z) { edge[++ct]=N(x,y,head[x],z);head[x]=ct; edge[++ct]=N(y,x,head[y],z);head[y]=ct; } void add1(int x,int y,int z) { ed[++ct1]=N(x,y,0,z); } bool cmp(N x,N y){return x.w>y.w;} void kruskal() { sort(ed+1,ed+ct1+1,cmp); for(int i=1,u,v;i<=ct1;i++) { u=ed[i].to; v=ed[i].hd; int a=find(u); int b=find(v); if(a!=b) { add(u,v,ed[i].w); fa[a]=b; } } } void dfs(int x,int f) { dep[x]=dep[f]+1; pre[x][0]=f; for(int i=head[x],u;i;i=edge[i].next) { u=edge[i].to; if(u==f)continue; mn[u][0]=edge[i].w; dfs(u,x); } } void lca(int x,int y) { int ans=inf; if(dep[x]>dep[y])swap(x,y); int d=dep[y]-dep[x]; for(int i=0;i<=17;i++) if((d>>i)&1)ans=min(ans,mn[y][i]),y=pre[y][i];//不是i-1! if(x==y) { printf("%d ",ans); return; } for(int i=17;i>=0;i--)//不是i>0 { if(pre[x][i]!=pre[y][i]) { ans=min(ans,min(mn[x][i],mn[y][i])); x=pre[x][i];y=pre[y][i]; } } ans=min(ans,min(mn[x][0],mn[y][0])); printf("%d ",ans); } int main() { int x,y,z; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d%d",&x,&y,&z),add1(x,y,z); for(int i=1;i<=n;i++)fa[i]=i; kruskal(); for(int i=1;i<=n;i++) if(!dep[i])dfs(i,0); for(int j=1;j<=17;j++) for(int i=1;i<=n;i++) { pre[i][j]=pre[pre[i][j-1]][j-1]; mn[i][j]=min(mn[i][j-1],mn[pre[i][j-1]][j-1]); } scanf("%d",&q); while(q--) { scanf("%d%d",&x,&y); if(find(x)!=find(y))printf("-1 "); else lca(x,y); } return 0; }