Luogu

分析

把边从大到小排序后建出 Kruskal 重构树。

那么答案就相当于 Kruskal 重构树上 LCA 的权值。随便用什么办法求 LCA 即可。

注意原图可能不连通,询问时要判一下连通性,而且预处理时每个连通块都要预处理到。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=20000+10,M=50000+10;

int n,m,tot;

struct edge { int u,v,w; } e[M];
bool operator <(edge a,edge b) { return a.w>b.w; }

int rt[N];
inline int find(int x) { return x==rt[x]?x:rt[x]=find(rt[x]); }

vector<int> E[N];
int w[N],dep[N],f[15][N];
inline void dfs(int u,int fa) {
    dep[u]=dep[fa]+1,f[0][u]=fa;
    for (re int i=1;i<15;++i) f[i][u]=f[i-1][f[i-1][u]];
    for (re int v:E[u]) dfs(v,u);
}
inline int getlca(int u,int v) {
    if (dep[u]<dep[v]) swap(u,v);
    for (re int i=14;~i;--i)
        if (dep[f[i][u]]>dep[v]) u=f[i][u];
    if (dep[u]!=dep[v]) u=f[0][u];
    for (re int i=14;~i;--i)
        if (f[i][u]!=f[i][v]) u=f[i][u],v=f[i][v];
    if (u!=v) u=f[0][u];
    return u;
}

int main() {
    tot=n=read(),m=read();
    for (re int i=1;i<=m;++i) e[i]=(edge){read(),read(),read()};
    sort(e+1,e+m+1);
    for (re int i=1;i<=n<<1;++i) rt[i]=i;
    for (re int i=1;i<=m;++i) {
        int u=find(e[i].u),v=find(e[i].v);
        if (u!=v) { ++tot;
            E[tot].push_back(u),rt[u]=tot;
            E[tot].push_back(v),rt[v]=tot;
            w[tot]=e[i].w;
        }
    }
    for (re int i=1;i<=tot;++i) if (!dep[i]) dfs(find(i),0);
    int Q=read();
    while (Q--) {
        int u=read(),v=read();
        if (find(u)!=find(v)) puts("-1");
        else printf("%d\n",w[getlca(u,v)]);
    }
    return 0;
}
最后修改:2019 年 10 月 13 日 05 : 22 PM