1 最小生成树
1.1 生成树
无向图 $G$ 的生成树,就是具有图 $G$ 的所有顶点,但是边数最小的联通子图
更加详细的定义: Wikipedia – 生成树
1.2 最小生成树
带权联通无向图的总权值最小的生成树
更加详细的定义: Wikipedia – 最小生成树
1.3 求解算法
- Kruskal 算法
- Prim 算法
有一些别的有意思的,甚至接近线性的算法,但是因为其不方便在 Oi 中出现,故此不做其他讨论
Prim 算法在稠密图具有优势,然而 Oi 中如果是稠密图要么就 Kruskal 也可以过,要么 Prim 也没用……
所以我们今天仅讨论 Kruskal 算法
2 Kruskal 算法
2.1 复杂度部分
- 时间 $O(E \log(V))$
- E 为边数, V 为点数
2.2 实现
- 对图 $G$ 中所有边排序
- 设图 $G’$ 只有图 $G$ 中所有的点,没有边
- 从小到大遍历
- 若当前这条边的两点不在同意联通块,则在图 $G’$ 连接两点
- 进入下一条边
- 图 $G’$ 即为图 $G$ 的最小生成树
2.3 证明
- 因为每次联通的边都是桥,所以图 $G’$ 一定是树
- 若 $u – v$ 之间有一条更短的边,则排序之后一定会更加靠前,优先被选择
2.4 代码
int k_ecnt;
struct k_edge{
int now, to, val;
bool operator< (const k_edge &b)const { return this -> val > b.val; }
}k_e[M << 1];
struct _set{
int fa[N];
inline void init(int now){
for(int i = 1; i <= now; i++)
fa[i] = i;
}
int get_fa(int now){
if( fa[now] == now )
return now;
return fa[now] = get_fa( fa[now] );
}
int& operator[] (int now) { return fa[now]; }
}set;
void kru(){
set.init(n);
std::sort(k_e + 1, k_e + k_ecnt + 1);
for(int i = 1; i <= k_ecnt; i++){
int tmp_now = set.get_fa( k_e[i].now ), tmp_to = set.get_fa( k_e[i].to );
if( tmp_now != tmp_to ){
add_edge(k_e[i].now, k_e[i].to, k_e[i].val);
add_edge(k_e[i].to, k_e[i].now, k_e[i].val);
set[ tmp_to ] = tmp_now;
}
}
}
3 Luogu P1967 火车运输
题目的意思精简一下就是 求 $u – v$ 路径上的最大边权
乍一看有一点最短路的味道(至少我人生中第一次看到这到题目的时候是这样子的)
但如果我们将问题是一棵树上,求两点之间最大边权就非常简单,要么倍增,要么树剖套线段树
那么问题来了,题目给的是一张无向图……
但是最大生成树满足这个性质,因为本生最小生成树就保证了链接两个不同联通分量最大的边权
所以先求最小生成树,然后跑倍增即可
3.1 代码
#include <cstdio>
#include <algorithm>
inline int Min(int a, int b) {return a < b? a: b;}
const int N = 11000;
const int M = 51000;
const int INF = 0x3f3f3f3f;
int n, m, q;
bool vis[N];
// edge start
struct edge{
int to, val, next;
}e[N << 1];
int ehead[N], ecnt;
inline void add_edge(int now, int to, int val){
ecnt ++;
e[ecnt].to = to;
e[ecnt].val = val;
e[ecnt].next = ehead[now];
ehead[now] = ecnt;
}
// edge end
// kru start
int k_ecnt;
struct k_edge{
int now, to, val;
bool operator< (const k_edge &b)const { return this -> val > b.val; }
}k_e[M << 1];
struct _set{
int fa[N];
inline void init(int now){
for(int i = 1; i <= now; i++)
fa[i] = i;
}
int get_fa(int now){
if( fa[now] == now )
return now;
return fa[now] = get_fa( fa[now] );
}
int& operator[] (int now) { return fa[now]; }
}set;
void kru(){
set.init(n);
std::sort(k_e + 1, k_e + k_ecnt + 1);
for(int i = 1; i <= k_ecnt; i++){
int tmp_now = set.get_fa( k_e[i].now ), tmp_to = set.get_fa( k_e[i].to );
if( tmp_now != tmp_to ){
add_edge(k_e[i].now, k_e[i].to, k_e[i].val);
add_edge(k_e[i].to, k_e[i].now, k_e[i].val);
set[ tmp_to ] = tmp_now;
}
}
}
// kru end
// st start
int dep[N], fa[N][21], Min_node[N][21];
void get_st(int now, int la){
vis[now] = true;
dep[now] = dep[la] + 1;
fa[now][0] = la;
for(int k = 1; k <= 20; k++){
fa[now][k] = fa[ fa[now][ k - 1 ] ][ k - 1 ];
Min_node[now][k] = Min(Min_node[now][ k - 1 ], Min_node[ fa[now][k - 1] ][ k - 1 ]);
}
for(int i = ehead[now]; i; i = e[i].next){
if( e[i].to == la )
continue;
Min_node[ e[i].to ][0] = e[i].val;
get_st(e[i].to, now);
}
}
// st end
int query(int from, int to){
int min = INF;
if( dep[from] < dep[to] ) { int tmp = to; to = from; from = tmp; }
for(int k = 20; k >= 0; k --){
if(dep[ fa[from][k] ] >= dep[to]){
min = Min(min, Min_node[from][k]);
from = fa[from][k];
}
}
if( from == to )
return min;
for(int k = 20; k >= 0; k --){
if(fa[from][k] != fa[to][k]){
min = Min(min, Min(Min_node[from][k], Min_node[to][k]));
from = fa[from][k];
to = fa[to][k];
}
}
min = Min(min, Min( Min_node[from][0], Min_node[to][0] ));
return min;
}
int main(){
#ifdef woshiluo
freopen("luogu.1967.in", "r", stdin);
freopen("luogu.1967.out", "w" ,stdout);
#endif
scanf("%d%d", &n, &m);
for(int i = 1, u, v, w; i <= m; i++){
scanf("%d%d%d", &u, &v, &w);
k_e[ ++ k_ecnt ] = (k_edge){u, v, w};
k_e[ ++ k_ecnt ] = (k_edge){v, u, w};
}
kru();
for(int i = 1; i <= n; i++){
if(!vis[i]){
get_st(i, 0);
// fa[i][0] = i; Min_node[i][0] = INF;
}
}
scanf("%d", &q);
int u, v;
while( q -- ) {
scanf("%d%d", &u, &v);
if( set.get_fa(u) != set.get_fa(v) ){
printf("-1\n");
continue;
}
printf("%d\n", query(u, v));
}
}
[…] 在 Kruskal 最小/大生成树 — Luogu P1967 货车运输 一文中,介绍了 Kruskal 算法是如何生成最小生成树的 […]