NOIP 2013 货车运输

RT,一道裸的 Kruskal 重构树题。因为存在点与点之间不连通的问题,所以在跑完 Kruskal 以后对每个树以并查集的根为根进行剖分求LCA。

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    
    //define
    const int maxn = 1e5 + 5;
    struct node{
        int u, v, w;
    }edge[maxn];
    struct graph{
        int v, next;
    }e[maxn];
    int n, m, tot, tot2, head[maxn], f[maxn], val[maxn];
    int size[maxn], fa[maxn], son[maxn], dep[maxn], top[maxn], vis[maxn];
    
    inline bool cmp(node a, node b){return a.w > b.w;}
    
    inline int find(int x){return x == f[x] ? x : f[x] = find(f[x]);}
    
    inline void addedge(int u, int v){
        e[++tot] = (graph){v, head[u]};
        head[u] = tot;
    }
    
    void dfs1(int u, int ft){
        size[u] = 1;vis[u] = 1;
        for(register int i = head[u]; i ; i = e[i].next){
            int v = e[i].v;
            if(v == ft)continue;
            dep[v] = dep[u] + 1;
            fa[v] = u;
            dfs1(v, u);
            size[u] += size[v];
            if(size[v] > size[son[u]])son[u] = v;
        }
    }
    
    void dfs2(int u, int tp){
        top[u] = tp;
        if(son[u])dfs2(son[u], tp);
        for(register int i = head[u]; i ; i = e[i].next){
            int v = e[i].v;
            if(v==son[u]||v==fa[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 = fa[top[u]];
            else v = fa[top[v]];
        }
        return dep[u] < dep[v] ? u : v;
    }
    
    void kruskal_build(){
        tot2 = n;
        for(register int i = 1; i <= n; ++i)f[i] = i;
        sort(edge + 1, edge + m + 1, cmp);
        for(register int i = 1; i <= m; ++i){
            int fa_u = find(edge[i].u);
            int fa_v = find(edge[i].v);
            if(fa_u != fa_v){
                val[++tot2] = edge[i].w;
                f[tot2] = f[fa_u] = f[fa_v] = tot2;
                addedge(fa_u, tot2);
                addedge(tot2, fa_u);
                addedge(fa_v, tot2);
                addedge(tot2, fa_v);
            }
        }
        for(register int i = 1; i <= tot; ++i){
            if(!vis[i]){
                int tmp = find(i);
                dfs1(tmp, 0);dfs2(tmp, tmp);
            }
        }
    }
    
    //main
    int main(){
        ios::sync_with_stdio(false);
        cin >> n >> m;
        for(register int i = 1; i <= m; ++i){
            cin >> edge[i].u >> edge[i].v >> edge[i].w;
        }
    
        kruskal_build();
    
        int t; cin >> t;
        while(t--){
            int uu, vv;cin >> uu >> vv;
            if(find(uu) != find(vv))cout << "-1" << endl;
            else cout << val[lca(uu, vv)] << endl;
        }
        return 0;
    }