BZOJ 3732 네트워크 Kruskal 재 구성 트 리

제목:n 개의 점 m 변 의 무방 향 연결 도 를 정 하고 k 번 은 두 점 사이 의 모든 경로 중 가장 긴 변 의 최소 값 을 묻는다.
Kruskal+LCA 배가 방법http://blog.csdn.net/popoqqq/article/details/39755703
LCT 방법http://blog.csdn.net/popoqqq/article/details/39929277
크 루 스 칼 재 구성 트 리 는 정말 강하 다...............................................................
한 변 을 넣 을 때마다 우 리 는 이 변 의 양 끝 점 을 연결 하지 않 고 이 변 의 양 끝 점 이 있 는 곳 을 조사 하고 집합 한 뿌리 를 연결 하 며 순서대로 합병 합 니 다.
이렇게 하 는 장점 은 모든 노드 에서 뿌리 까지 의 경로 길이 가 logn 을 초과 하지 않 는 다 는 것 이다.
또한 Kruskal 재 구성 트 리 의 성질 로 인해 두 점 사이 의 가장 긴 변 은 원래 그림 과 같 고 가장 긴 변 의 한 끝 이 연 결 된 것 은 반드시 두 점 의 LCA 이다.
그 러 니까 그냥 폭력 으로 위로 찾 으 면 돼 요.배가 되면 O(loglogn)로 최적화 할 수 있 을 것 같 아 요.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 15100
using namespace std;
struct abcd{
    int x,y,f;
    bool operator < (const abcd &Y) const
    {
        return f < Y.f ;
    }
}edges[M<<1];
int n,m,k;
int belong[M],fa[M],size[M],dis[M],dpt[M];
int Find(int x)
{
    if(!belong[x])
        belong[x]=x,size[x]=1;
    if(belong[x]==x)
        return x;
    return belong[x]=Find(belong[x]);
}
int Get_Depth(int x)
{
    if(dpt[x]) return dpt[x];
    if(!fa[x]) return dpt[x]=1;
    return dpt[x]=Get_Depth(fa[x])+1;
}
void Kruskal()
{
    int i;
    sort(edges+1,edges+m+1);
    for(i=1;i<=m;i++)
    {
        int x=Find(edges[i].x);
        int y=Find(edges[i].y);
        if(x==y) continue ;
        if(size[x]>size[y])
            swap(x,y);
        belong[x]=y;
        size[y]=max(size[y],size[x]+1);
        fa[x]=y;
        dis[x]=edges[i].f;
    }
}
int Query(int x,int y)
{
    int re=0;
    if(dpt[x]<dpt[y])
        swap(x,y);
    while(dpt[x]>dpt[y])
        re=max(re,dis[x]),x=fa[x];
    while(x!=y)
        re=max(re,dis[x]),re=max(re,dis[y]),x=fa[x],y=fa[y];
    return re;
}
int main()
{
    int i,x,y;
    cin>>n>>m>>k;
    for(i=1;i<=m;i++)
        scanf("%d%d%d",&edges[i].x,&edges[i].y,&edges[i].f);
    Kruskal();
    for(i=1;i<=n;i++)
        Get_Depth(i);
    for(i=1;i<=k;i++)
    {
        scanf("%d%d",&x,&y);
        printf("%d
", Query(x,y) );
    }
}