【学习】Kruskal重构树

## 介绍

求图中任意两点最大边权最小或最小边权最大

## 题目

1.BZOJ3732 Network

模板题。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<vector>
#include<stack>
#include<cmath>
#include<bits/stdc++.h>
#define ri register int
#define ll long long
#define For(i,l,r) for(ri i=l;i<=r;i++)
#define Dfor(i,r,l) for(ri i=r;i>=l;i--)
using namespace std;
const int M=200010;
int n,m,cnt,q,fa[M],tot,head[M],val[M],size[M],top[M],son[M],dep[M],f[M];
struct node{
    int u,v,dis;
    bool operator < (const node&x) const{
        return dis<x.dis;
    }
}e[M];
inline bool cmp(node x,node y){return x.dis<y.dis;}
struct Node{
    int nxt,to;
}ee[M];
inline ll read(){
    ll f=1,sum=0;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){sum=(sum<<1)+(sum<<3)+(ch^48);ch=getchar();}
    return f*sum;
}
inline int getfa(int x){
    if(x==fa[x]) return x;
    return fa[x]=getfa(fa[x]);
}
inline void add(int u,int v){
    ee[++tot].nxt=head[u];
    head[u]=tot;
    ee[tot].to=v;
}
inline void dfs1(int u,int pa){
    size[u]=1;
    for(ri i=head[u];i;i=ee[i].nxt){
        int v=ee[i].to;
        if(v==pa)continue;
        dep[v]=dep[u]+1;f[v]=u;
        dfs1(v,u);
        size[u]+=size[v];
        if(size[v]>size[son[u]]) son[u]=v;
    }
}
inline void dfs2(int u,int tp){
    top[u]=tp;
    if(son[u]) dfs2(son[u],tp);
    for(ri i=head[u];i;i=ee[i].nxt){
        int v=ee[i].to;
        if(v==son[u]||v==f[u]) continue;
        dfs2(v,v);
    }
}
inline int lca(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]>dep[top[v]]) u=f[top[u]];
        else v=f[top[v]];
    }
    if(dep[u]<dep[v]) return u;
    return v;
}
inline void kruskal(){
    For(i,1,n) fa[i]=i;
    sort(e+1,e+m+1);
    For(i,1,m){
        int fu=getfa(e[i].u),fv=getfa(e[i].v);
        if(fu!=fv){
            val[++cnt]=e[i].dis;
            fa[cnt]=fa[fu]=fa[fv]=cnt;
            add(fu,cnt),add(cnt,fu);
            add(fv,cnt),add(cnt,fv);
        }
    }
    dfs1(cnt,0),dfs2(cnt,cnt);
}
int main(){
    n=read(),m=read(),q=read(),cnt=n;
    For(i,1,m){
        e[i].u=read(),e[i].v=read(),e[i].dis=read();
    }
    kruskal();
    while(q--){
        int u=read(),v=read();
        printf("%d
",val[lca(u,v)]);
    }
    return 0;
}

 2.P1967 货车运输

模板题。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<vector>
#include<stack>
#include<cmath>
#include<bits/stdc++.h>
#define ri register int
#define ll long long
#define For(i,l,r) for(ri i=l;i<=r;i++)
#define Dfor(i,r,l) for(ri i=r;i>=l;i--)
using namespace std;
const int M=200010;
int n,m,cnt,q,fa[M],tot,head[M],val[M],size[M],top[M],son[M],dep[M],f[M];
bool vis[M];
struct node{
    int u,v,dis;
    bool operator < (const node&x) const{
        return dis<x.dis;
    }
}e[M];
inline bool cmp(node x,node y){return x.dis>y.dis;}
struct Node{
    int nxt,to;
}ee[M];
inline ll read(){
    ll f=1,sum=0;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){sum=(sum<<1)+(sum<<3)+(ch^48);ch=getchar();}
    return f*sum;
}
inline int getfa(int x){
    if(x==fa[x]) return x;
    return fa[x]=getfa(fa[x]);
}
inline void add(int u,int v){
    ee[++tot].nxt=head[u];
    head[u]=tot;
    ee[tot].to=v;
}
inline void dfs1(int u,int pa){
    size[u]=1;vis[u]=1;
    for(ri i=head[u];i;i=ee[i].nxt){
        int v=ee[i].to;
        if(v==pa)continue;
        dep[v]=dep[u]+1;f[v]=u;
        dfs1(v,u);
        size[u]+=size[v];
        if(size[v]>size[son[u]]) son[u]=v;
    }
}
inline void dfs2(int u,int tp){
    top[u]=tp;
    if(son[u]) dfs2(son[u],tp);
    for(ri i=head[u];i;i=ee[i].nxt){
        int v=ee[i].to;
        if(v==son[u]||v==f[u]) continue;
        dfs2(v,v);
    }
}
inline int lca(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]>dep[top[v]]) u=f[top[u]];
        else v=f[top[v]];
    }
    return dep[u]<dep[v]?u:v;
}
inline void kruskal(){
    For(i,1,n) fa[i]=i;
    sort(e+1,e+m+1,cmp);
    For(i,1,m){
        int fu=getfa(e[i].u),fv=getfa(e[i].v);
        if(fu!=fv){
            val[++cnt]=e[i].dis;
            fa[cnt]=fa[fu]=fa[fv]=cnt;
            add(fu,cnt),add(cnt,fu);
            add(fv,cnt),add(cnt,fv);
        }
    }
    For(i,1,cnt){
        if(!vis[i]){
            int ff=getfa(i);
            dfs1(ff,0),dfs2(ff,ff);
        }
    }
}
int main(){
    n=read(),m=read(),cnt=n;
    For(i,1,m){
        e[i].u=read(),e[i].v=read(),e[i].dis=read();
    }
    kruskal();
    q=read();
    while(q--){
        int u=read(),v=read();
        if(getfa(u)!=getfa(v)) printf("-1
");
        else printf("%d
",val[lca(u,v)]);
    }
    return 0;
}