标题链接：传送门
kruskal重构树
那么这是个什么东西呢？
结构很简单
咱们在结构生成树的时分
每遇到两个不在同一调集的节点
就新建一个节点并将这个节点设为那两个节点的父亲
将新建节点的权值设为本来两个节点之间的边权
这样就将边权转化成了点权
由于咱们的边权是有序的
所以重构出的树的根节点的权值一定是最大的或者是最小的
能够举一个比方自己结构试一下
比方：
1 3 2
3 4 4
1 2 5
2 4 6
2 3 11
结构出来应该是这个样子的----
567便是咱们新建出来的节点
点权能够自己画上试试
这样两个点的lca的点权便是两点途径边权最大的最小值
由于边权越大的边构成的点越靠上
所以这样走的是最小的边权
代码也很好写
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define A 1000010
#define B 2010
using namespace std;
typedef long long ll;
struct node {
int next, to;
}e[A];
int head[A], num;
void add(int fr, int to) {
e[++num].next = head[fr];
e[num].to = to;
head[fr] = num;
}
struct Edge {
int a, b, c;
friend bool operator < (const Edge a, const Edge b) {
return a.c < b.c;
}
}p[A];
int n, m, k, w[A], cnt, fa[A], a, b;
int find(int x) {
if (fa[x] == x) return x;
else return fa[x] = find(fa[x]);
}
int siz[A], faa[A], dep[A], son[A], dfn[A], ctt, top[A];
void prepare(int fr) {
siz[fr] = 1;
for (int i = head[fr]; i; i = e[i].next) {
int ca = e[i].to;
if (ca == faa[fr]) continue;
faa[ca] = fr;
dep[ca] = dep[fr] + 1;
prepare(ca);
siz[fr] += siz[ca];
if (siz[ca] > siz[son[fr]]) son[fr] = ca;
}
}
void dfs(int fr, int tp) {
dfn[fr] = ++ctt, top[fr] = tp;
if (son[fr]) dfs(son[fr], tp);
for (int i = head[fr]; i; i = e[i].next) {
int ca = e[i].to;
if (ca == faa[fr] or ca == son[fr]) continue;
dfs(ca, ca);
}
}
int lca(int x, int y) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
x = faa[top[x]];
}
return dep[x] < dep[y] ? w[x] : w[y];
}
int main(int argc, char const *argv[]) {
cin >> n >> m >> k;
for (int i = 1; i <= m; i++) scanf("%d%d%d", &p[i].a, &p[i].b, &p[i].c);
sort(p + 1, p + m + 1); cnt = n;
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 1; i <= m; i++) {
int fx = find(p[i].a), fy = find(p[i].b);
if (fx == fy) continue;
w[++cnt] = p[i].c;
fa[cnt] = fa[fx] = fa[fy] = cnt;
add(cnt, fx); add(fx, cnt);
add(cnt, fy); add(fy, cnt);
}
prepare(cnt); dfs(cnt, 0);
while (k--) {
scanf("%d%d", &a, &b);
printf("%d
", lca(a, b));
}
}
