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;
}