BZOJ3732 LCA
#include
using namespace std;
const int N=1e5+10;
int head[N],Next[N],ver[N],edge[N],mf[N][20],f[N][20],d[N],fa[N],tot,t;
queue q;
struct P{
int x,y,z;
}A[N];
bool cmp(P a,P b){
return a.zd[y])swap(x,y);
int val=0;
for(int i=t;i>=0;--i)
if(d[f[y][i]]>=d[x])val=max(val,mf[y][i]),y=f[y][i];
//cout<=0;--i){
if(f[x][i]!=f[y][i])val=max(val,max(mf[x][i],mf[y][i])),x=f[x][i],y=f[y][i];
}
return max(val,max(mf[x][0],mf[y][0]));
}
int main(){
//freopen("1.in","r",stdin);
int n,m,k,x,y;
scanf("%d%d%d",&n,&m,&k);
t=int(log(n)/log(2))+1;
for(int i=1;i<=m;++i)scanf("%d%d%d",&A[i].x,&A[i].y,&A[i].z);
sort(A+1,A+1+m,cmp);
for(int i=1;i<=n;++i)fa[i]=i;
int ans=0;
for(int i=1;i<=m;++i){
int x=get(A[i].x);int y=get(A[i].y);
if(x==y)continue;
fa[x]=y;
add(A[i].x,A[i].y,A[i].z);
add(A[i].y,A[i].x,A[i].z);
++ans;
}
bfs();
for(int i=1;i<=k;++i){
scanf("%d%d",&x,&y);
printf("%d
",lca(x,y));
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU 1874: 원활 한 공사 계속 [Dijkstra & SPFA & Floyd]모 성 은 여러 해 동안 의 원활 한 공사 계획 을 실행 한 후에 마침내 많은 길 을 건설 하 였 다.길 을 많이 건 너 지 않 아 도 좋 지 않다. 한 도시 에서 다른 도시 로 갈 때마다 여러 가지 도로 방안 을 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.