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 实现

1. 对图 $G$ 中所有边排序
2. 设图 $G’$ 只有图 $G$ 中所有的点，没有边
3. 从小到大遍历
   1. 若当前这条边的两点不在同意联通块，则在图 $G’$ 连接两点
   2. 进入下一条边
4. 图 $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 火车运输

题目链接: https://www.luogu.org/problemnew/show/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));
    }
}