最小生成树弄出来倍增就没了
和NOIP的货车运输没什么区别
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=15005;
int n,m,f[N],k,cnt,dep[N],fa[N][15],V[N][15],en,h[N];
struct Ed{
int a,b,v;
friend bool operator<(Ed A,Ed B){return A.v<B.v;}
}es[N<<1];
struct Edge{
int b,v,next;
}e[N<<1];
void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}
int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
int LCA(int u,int v){
if(dep[u]<dep[v])swap(u,v);
int deep=dep[u]-dep[v],Mx=-1;
for(int i=0;i<=14;i++)if(deep&(1<<i)){Mx=max(Mx,V[u][i]);u=fa[u][i];}
for(int i=14;i>=0;i--){
if(fa[u][i]!=fa[v][i]){Mx=max(Mx,max(V[u][i],V[v][i]));u=fa[u][i];v=fa[v][i];}
}
return u==v?Mx:max(Mx,max(V[u][0],V[v][0]));
}
void Prepare(){
for(int i=1;i<=14;i++){
for(int j=1;j<=n;j++){
fa[j][i]=fa[fa[j][i-1]][i-1];
V[j][i]=max(V[j][i-1],V[fa[j][i-1]][i-1]);
}
}
}
void dfs(int u,int fat){
for(int i=h[u];i;i=e[i].next){
int v=e[i].b;
if(v==fat)continue;
fa[v][0]=u;
dep[v]=dep[u]+1;
V[v][0]=e[i].v;
dfs(v,u);
}
}
int main(){
freopen("3732.in","r",stdin);
freopen("3732.out","w",stdout);
scanf("%d %d %d",&n,&m,&k);
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++)scanf("%d %d %d",&es[i].a,&es[i].b,&es[i].v);
sort(es+1,es+m+1);
for(int i=1;i<=m && cnt<n-1;i++){
if(Find(es[i].a)!=Find(es[i].b)){
AddEdge(es[i].a,es[i].b,es[i].v);
AddEdge(es[i].b,es[i].a,es[i].v);
cnt++;
f[Find(es[i].a)]=Find(es[i].b);
}
}
dfs(1,0);
Prepare();
for(int i=1;i<=k;i++){
int u,v;
scanf("%d %d",&u,&v);
printf("%d\n",LCA(u,v));
}
return 0;
}
评论 (0)
