[BZOJ 3732] Network - Kruskal 重构树

ajcxsu
ajcxsu 2018年03月20日
  • 24 次阅读

Problem

给你N个点的无向图 (1 <= N <= 15,000),记为:1…N。
图中有M条边 (1 <= M <= 30,000) ,第j条边的长度为: d_j ( 1 < = d_j < = 1,000,000,000).

现在有 K个询问 (1 < = K < = 20,000)。
每个询问的格式是:A B,表示询问从A点走到B点的所有路径中,最长的边最小值是多少?

Solution

不再赘述。

传送门:https://www.cnblogs.com/ZegWe/p/6243883.html

感觉自己打得好傻逼...

Code

// Code by ajcxsu
// Problem: Network

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10, M=3e4+10;
struct Edge {
    int u,v,w;
} e[M];
bool cmp(const Edge &a, const Edge &b) { return a.w<b.w; }
int n,m,q;

int f[N],l[N],r[N],fa[N],w[N],p;
int Find(int x) {
    if(!fa[x]) return x;
    return fa[x]=Find(fa[x]);
}

int siz[N],dep[N],son[N],idx;
int dfn[N],top[N];
void dfs1(int x,int k) {
    dep[x]=k, siz[x]=1;

    if(l[x]!=0) {
        dfs1(l[x],k+1);
        siz[x]+=siz[l[x]];
        if(siz[l[x]]>siz[son[x]]) son[x]=l[x];
    }
    if(r[x]!=0) {
        dfs1(r[x],k+1);
        siz[x]+=siz[r[x]];
        if(siz[r[x]]>siz[son[x]]) son[x]=r[x];
    }
}
void dfs2(int x,int t) {
    dfn[x]=++idx;
    top[x]=t;
    if(son[x]) dfs2(son[x],t);
    if(l[x]!=son[x] && l[x]) dfs2(l[x],l[x]);
    if(r[x]!=son[x] && r[x]) dfs2(r[x],r[x]);
}

int lca(int s,int t) {
    while(top[s]!=top[t]) {
        if(dep[top[s]]<dep[top[t]]) swap(s,t);
        s=f[top[s]];
    }
    return dep[s]<dep[t]?s:t;
}

int main() {
    ios::sync_with_stdio(false);
    cin>>n>>m>>q;
    p=n;
    for(int i=0;i<m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e,e+m,cmp);
    for(int i=0;i<m;i++) {
        int u=e[i].u, v=e[i].v;
        int af=Find(u), bf=Find(v);
        if(af==bf) continue;
        l[++p]=af, r[p]=bf;
        f[af]=f[bf]=fa[af]=fa[bf]=p;
        w[p]=e[i].w;
    }
    dfs1(p,1);
    dfs2(p,p);
    int u,v;
    for(int i=0;i<q;i++) {
        cin>>u>>v;
        cout<<w[lca(u,v)]<<endl;
    }
    return 0;
}

本文链接:https://acxblog.site/archives/sol-bzoj-3732.html
本文采用 CC BY-NC-SA 3.0 协议进行许可