适用场合
多次询问在一个图中,两个点之间的最短路上的最长边。
这个题有多种解法,用
K
r
u
s
k
a
l
Kruskal
Kruskal重构树的方法当然也能解决。
主要思想
建一个新的树
-
按照Kruskal算法依次遍历边,当要进行合并时,再执行以下操作
-
把最小生成树上的边 ( u , v , w ) (u,v,w) (u,v,w)当作新的点,权值为原来边权 w w w
-
分别两条边连向 u u u, v v v所在的子树的根节点
求两个点 x , y x,y x,y之间最短路上的最长边,等价于在新的树上 L C A ( x , y ) LCA(x,y) LCA(x,y)的权值。
代码
这个是用来解决货车运输的代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxN = 1e5 + 7;
int n, m, q, cnt, head[maxN], fa[maxN], tot, val[maxN], f[maxN][21], depth[maxN];
struct Edge {
int from, to, dis;
}e[maxN << 1], initEdge[maxN];
inline void add(int u, int v)
{
e[++cnt].from = head[u];
e[cnt].to = v;
head[u] = cnt;
}
int Find(int x)
{
return fa[x] == x? x : fa[x] = Find(fa[x]);
}
bool cmp(Edge x, Edge y)
{
return x.dis > y.dis;
}
void dfs(int x)
{
for(int i = head[x]; i; i = e[i].from) {
int y = e[i].to;
f[y][0] = x; depth[y] = depth[x] + 1;
dfs(y);
}
}
inline void KruskalTree()
{
sort(initEdge + 1, initEdge + 1 + m, cmp);
for(int i = 1; i <= n; ++i)
fa[i] = i;
tot = n; //tot记录的是新的图上点的个数
for(int i = 1; i <= m; ++i) {
int fx = Find(initEdge[i].from), fy = Find(initEdge[i].to);
if(fx == fy)
continue;
val[++tot] = initEdge[i].dis; //建立新的树
fa[tot] = fa[fx] = fa[fy] = tot;
add(tot, fx); add(tot, fy);
}
}
inline void initLca() //从这开始就是普通的LCA了
{
for(int i = tot; i >= 0; --i)
if(!depth[i])
dfs(i);
for(int j = 1; (1 << j) <= tot; ++j)
for(int i = 1; i <= tot; ++i)
f[i][j] = f[f[i][j - 1]][j - 1];
}
int Lca(int x, int y)
{
if(depth[x] < depth[y])
swap(x, y);
int t = (int)(log(depth[x]) / log(2)) + 1;
for(int i = t; i >= 0; i--)
if(depth[f[x][i]] >= depth[y])
x = f[x][i];
if(x == y)
return x;
for(int i = t; i >= 0; i--)
if(f[x][i] != f[y][i])
x = f[x][i], y = f[y][i];
return f[x][0];
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++i)
scanf("%d%d%d", &initEdge[i].from, &initEdge[i].to, &initEdge[i].dis);
KruskalTree();
initLca();
scanf("%d", &q);
while(q--) {
int x, y;
scanf("%d%d", &x, &y);
if(Find(x) != Find(y)) //当然图可能不连通
printf("-1\n");
else
printf("%d\n", val[Lca(x, y)]);
}
return 0;
}