生成树学习笔记

vectorxyz · 2024-08-25 09:12:04 · 算法·理论

【-1】前言

以下内容仅个人理解，如有任何不对请 踹本唐氏一下。（本文重点在将次小生成树，最小生成树一笔带过）。

修改记录：

Upd 2024.8.26：完成主体。

【1】最小生成树

我先要了解一下什么是最小生成树（来自 \tt{OI-Wiki}）。

我们定义无向连通图的 最小生成树（Minimum Spanning Tree，MST）为边权和最小的生成树。注意：只有连通图才有生成树，而对于非连通图，只存在生成森林。

Kruskal 求最小生成树

先扔一道题：P3366 【模板】最小生成树。

再扔一个图：

这就是 Kruskal 是执行示意图，这个算法就是贪心的加边，然后排除无用边即可，大家应该都会吧我不想多说。

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
int fa[N];
struct node
{
    int u, v, w;
}g[N];

int n, m;
int tot, ans;
int find(int x)
{
    if(fa[x] == x) return x;
    else return fa[x] = find(fa[x]);
}
bool cmp(node a, node b){ return a.w < b.w; }
void kruskal()
{
    sort(g + 1, g + 1 + m, cmp);
    for(int i = 1;i <= m;i ++ ){
        int u = find(g[i].u);
        int v = find(g[i].v);
        if(u == v) continue;
        ans += g[i].w;
        fa[v] = u;
        tot ++ ;
        if(tot == n - 1) break;
    }
}

int main()
{
    cin >> n >> m;

    for(int i = 1;i <= n;i ++ ) fa[i] = i;
    for(int i = 1;i <= m;i ++ ) 
    {
        cin >> g[i].u >> g[i].v >> g[i].w;
    }
    kruskal();
    if(tot != n - 1) cout << "orz";
    else cout << ans << endl;
    return 0;
}

【2】次小生成树

次小生成树，顾名思义，就是权值和第二小的子树，而非严格第二小，及第二小有可能和最小值相等。

我们可以将所有生成树求出来，然后进行排序，这样就得到了次小生成树，但是时间复杂度太高了，不可取。

我们考虑优化，首先我们要知道一个结论，次小生成树和最小生成树之间只有一条边不相同（显而易见）。

所以我们先跑一遍最小生成树，记录一下权值和（记为 \text{Ans}）和已用边，然后在未用边中不断匹配，在最小生成树上找 e_i 到 e_j 最大值，记最大值为 \text{Max}，则答案为 \text{Ans} - \text{Max} - \text{w}（\text{w} 是当前边权值）。

那么我们如何找到树上两点边权最值呢？我们自然而然就想到了树剖。

然后代码就很好写了，但不给出 我不会告诉你是因为我没写的qwq!

【3】严格次小生成树

扔个题：P4180 [BJWC2010] 严格次小生成树。

严格次小生成树难度相对于次小生成树提升不少，我们在次小生成树解法上考虑怎么改，我们树剖的时候记录一个次大生值，如果最大值和当前边权相等，我们就换次大值上。

这中间有一个转化的过程，把最小生成树上最大边换成一个次小边，转换为如果树上最大值和当前边边权一样，就改次大值；其他情况和次小生成树一样。

代码

线段树部分：

struct Segment
{
    struct node
    {
        int l, r, ma, mex;
    }tr[N << 2];
    int get(int a, int b, int c, int d)
    {
        int yexo[4] = {a, b, c, d};
        sort(yexo, yexo + 4, greater<int>());
        for(int i = 1;i < 4;i ++ ){
            if(yexo[i] != yexo[0]) return yexo[i];
        }
        return yexo[0];
    }//比较次小值
    void build(int u, int l, int r)
    {
        if(l == r) {
            tr[u].ma = a[l];
            return ;
        }
        int mid = (l + r) / 2;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        tr[u].ma = max(tr[u << 1].ma, tr[u << 1 | 1].ma);
        tr[u].mex = get(tr[u << 1].ma, tr[u << 1 | 1].ma, tr[u << 1].mex, tr[u << 1 | 1].mex);
    }
    PII query(int u, int l, int r, int ll, int rr)
    {
        if(ll > r || rr < l) return make_pair(LONG_LONG_MIN, LONG_LONG_MIN);
        if(ll <= l && r <= rr) {
            return {tr[u].ma, tr[u].mex};
        }
        int mid = (l + r) / 2;
        PII x = query(u << 1, l, mid, ll, rr), y = query(u << 1 | 1, mid + 1, r, ll, rr);
        return {max(x.first, y.first), get(x.first, y.first, x.second, y.second)};
    }//模板
}seg;

树剖部分：

值得注意的是，这是边权树剖，注意处理。

struct TreePou
{
    void dfs1(int u, int F, int deep)
    {
        dep[u] = deep;
        fa[u] = F;
        sz[u] = 1;
        int maxn = -1;
        for(int i = head[u];i;i = e[i].next){
            int v = e[i].v;
            if(v == F) continue;
            w[v] = w[u] + e[i].w; 
            dfs1(v, u, deep + 1);
            sz[u] += sz[v];
            if(sz[v] > maxn){
                maxn = sz[v];
                son[u] = v;
            }
        }
    }
    void dfs2(int u, int topf)
    {
        top[u] = topf;
        id[u] = ++idx;
        a[idx] = w[u] - w[fa[u]]; // 类似于前缀和
        if(!son[u]) return ;
        dfs2(son[u], topf);
        for(int i = head[u];i;i = e[i].next){
            int v = e[i].v;
            if(v == fa[u] || v == son[u]) continue;
            dfs2(v, v);
        }
    }
    void init(){
        dfs1(1, 0, 1), dfs2(1, 1), seg.build(1, 1, n);
    }
    int Find(int x, int y, int w){
    int res = LONG_LONG_MIN;
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        PII k = seg.query(1, 1, n, id[top[x]], id[x]);
        res = max(res, (k.first == w) ? k.second : k.first);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    PII k = seg.query(1, 1, n, id[x] + 1, id[y]);
    res = max(res, (k.first == w) ? k.second : k.first);
    return res;
}
}tp;

然后处理一下细节拼接即可。

代码较长。

#include <bits/stdc++.h>
#define int long long

using namespace std;
typedef pair<int, int> PII;
int n, m;
const int N = 1e5 + 5, M = 3e5 + 5;
struct node
{
    int u, v, w;
}g[M << 1];
struct Edge
{
    int v, w, next;
}e[N << 2];
bool cmp(node a, node b){return a.w < b.w;}
int tot, head[N << 2];
void add(int u, int v, int w){e[++tot].v = v, e[tot].w = w, e[tot].next = head[u], head[u] = tot;}
int f[N], fa[N];
int top[N], sz[N], son[N], id[N], a[N], idx, dep[N], w[N];
bool vis[N];
int ans0, _, ans = LONG_LONG_MAX;

struct Kruskal
{
    int find(int x)
    {
        if(f[x] == x) return x;
        else return f[x] = find(f[x]);
    }
    void init()
    {
        for(int i = 1;i <= n;i ++ ) f[i] = i;
        for(int i = 1;i <= m;i ++ ) cin >> g[i].u >> g[i].v >> g[i].w;
    }
    void work()
    {
        init();
        sort(g + 1, g + 1 + m, cmp);
        for(int i = 1;i <= m;i ++ ){
            int x = find(g[i].u), y = find(g[i].v);
            if(x == y) continue;
            add(g[i].u, g[i].v, g[i].w), add(g[i].v, g[i].u, g[i].w);
            vis[i] = 1;
            ans0 += g[i].w;
            f[y] = x;
            if(++_ == n - 1) break;
        }
    }
}kru;
struct Segment
{
    struct node
    {
        int l, r, ma, mex;
    }tr[N << 2];
    int get(int a, int b, int c, int d)
    {
        int yexo[4] = {a, b, c, d};
        sort(yexo, yexo + 4, greater<int>());
        for(int i = 1;i < 4;i ++ ){
            if(yexo[i] != yexo[0]) return yexo[i];
        }
        return yexo[0];
    }
    void build(int u, int l, int r)
    {
        if(l == r) {
            tr[u].ma = a[l];
            return ;
        }
        int mid = (l + r) / 2;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        tr[u].ma = max(tr[u << 1].ma, tr[u << 1 | 1].ma);
        tr[u].mex = get(tr[u << 1].ma, tr[u << 1 | 1].ma, tr[u << 1].mex, tr[u << 1 | 1].mex);
    }
    PII query(int u, int l, int r, int ll, int rr)
    {
        if(ll > r || rr < l) return make_pair(LONG_LONG_MIN, LONG_LONG_MIN);
        if(ll <= l && r <= rr) {
            return {tr[u].ma, tr[u].mex};
        }
        int mid = (l + r) / 2;
        PII x = query(u << 1, l, mid, ll, rr), y = query(u << 1 | 1, mid + 1, r, ll, rr);
        return {max(x.first, y.first), get(x.first, y.first, x.second, y.second)};
    }
}seg;

struct TreePou
{
    void dfs1(int u, int F, int deep)
    {
        dep[u] = deep;
        fa[u] = F;
        sz[u] = 1;
        int maxn = -1;
        for(int i = head[u];i;i = e[i].next){
            int v = e[i].v;
            if(v == F) continue;
            w[v] = w[u] + e[i].w; 
            dfs1(v, u, deep + 1);
            sz[u] += sz[v];
            if(sz[v] > maxn){
                maxn = sz[v];
                son[u] = v;
            }
        }
    }
    void dfs2(int u, int topf)
    {
        top[u] = topf;
        id[u] = ++idx;
        a[idx] = w[u] - w[fa[u]];
        if(!son[u]) return ;
        dfs2(son[u], topf);
        for(int i = head[u];i;i = e[i].next){
            int v = e[i].v;
            if(v == fa[u] || v == son[u]) continue;
            dfs2(v, v);
        }
    }
    void init(){
        dfs1(1, 0, 1), dfs2(1, 1), seg.build(1, 1, n);
    }
    int Find(int x, int y, int w){
    int res = LONG_LONG_MIN;
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        PII k = seg.query(1, 1, n, id[top[x]], id[x]);
        res = max(res, (k.first == w) ? k.second : k.first);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    PII k = seg.query(1, 1, n, id[x] + 1, id[y]);
    res = max(res, (k.first == w) ? k.second : k.first);
    return res;
}
}tp;

signed main()
{
    cin >> n >> m;
    kru.work();
    tp.init();
    for(int i = 1;i <= m;i ++ ){
        if(!vis[i]){
            int temp = ans0 - tp.Find(g[i].u, g[i].v, g[i].w) + g[i].w;
            if(ans > temp && temp > ans0 && temp != ans0 + e[i].w){
                ans = temp;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

【-2】鸣谢

参考资料：

• 最小生成树 - Oi wiki。
• 严格次小生成树 - Nemlitの专栏。

以及 我的义父 do_it_tomorrow 大佬的帮助。