Solves

Author: lllyouo
Date: 20250225
tag: 最小生成树计数
link: https://www.luogu.com.cn/problem/P4208

问题描述

link

分析

如果给定图 $G$ 不存在相同的边权，那么最小生成树是唯一的，反之则最小生成树不唯一。若图 $G$ 存在最小生成树 $T$ 与 $T^{'}$ ，根据 Kruskal 算法执行过程可以得到如下性质：

$T$ 的边权从小到大为 $w (t_{1}), w (t_{2}), w (t_{3}) \dots w (t_{s})$ ， $T^{'}$ 的边权从小到大为 $w (t_{1}^{'}), w (t_{2}^{'}), w (t_{3}^{'}) \dots w (t_{s}^{'})$ 必有 $w (t_{i}) = w (t_{i}^{'}) (1 \leq i \leq s)$ 。
若 $T$ 和 $T^{'}$ 都从零由小到大逐步加边，每种权值的边加完后图的连通性相同。
假设在最小生成树 $T$ 种，权值为 $w$ 的边有 $k$ 条，用任意 $k$ 条权值为 $w$ 的边替换 $T$ 中权值为 $w$ 的边且不产生环的最小生成树都是一颗合法的最小生成树。

我们可以将给定图 $G$ 边权值相同的边分成 $k$ 个组，同一个图的不同最小生成树之间，每个边组中用的边的个数是一样的。首先求解得到图 $G$ 的最小生成树，在生成树算法的计算过程中记录第 $i$ 种权值的边的个数 $T_{i}$ 。接下来借助搜索统计，第 $i$ 种权值的边数量 $T_{i}$ 是可以构成同一连通状态时的方法数，然后根据乘法原理计数即可。

具体来说，首选通过 kruskal 算法计算给定图的最小生成树 $T$ ， $T$ 的边权从小到大依次为 $w (t_{1}), w (t_{2}), w (t_{3}) \dots w (t_{s})$ ，在计算过程中统计每种权值的边在最小生成树中的数量。假设最小生成树中第 $i$ 种权值的边有 $a_{i}$ 条，仅需要求出第 $i$ 种权值的边选 $a_{i}$ 条不构成环的组合方式，接下来枚举每一种权值的边进行搜索，得到每一种权值的边的可行方案数 $c n t_{i}$ ，最后根据乘法原理统计答案即可。

如何求解 $c n t_{i}$ ？在 kruskal 算法执行前，图中边的权值已经从小到大排序完毕，即权值相同的边集中在一个区域，将边按照权值大小分成 $n u m$ 类，利用数组 $(l, r, c n t)$ 记录第 $i$ 类边的所在区间的起点序号、终点序号以及其在最小生成树种使用数量。接下来将并查集初始化，枚举每种权值的边进行搜索，对于每一类边中的所有边逐一试探，如果加入该边不构成环，即可加入该边，并统计该类边加入最小生成树的数量 $k$ ，如果加入该边构成环，则不加入该边。最后当该类边枚举结束，且 $k = c n t$ 时，该类边加入最小生成树的方法数 $c n t_{i}$ 加一。

参考代码

cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 110, M = 1010, MOD = 31011;
struct Edge {
    int u, v, w;

    bool operator< (const Edge& x) {
        return w < x.w;
    }
} e[M];

struct Node {
    // l 相同边权的边的起点序号
    // r 相同边权的边的终点序号
    // cnt 选入生成树的某权值的边在生成树中的数量
    int l, r, cnt;
} ed[1010];

int n, m, ans, num, cnt, p[110];

// 不进行路径压缩
int find(int x) {
    if (x == p[x]) return x;
    return find(p[x]);
}

void dfs(int x, int now, int k) {
    if (now == ed[x].r + 1) {
        if (k == ed[x].cnt) cnt++; // 确保与生成树所需边数相同
        return ;
    }

    int fu = find(e[now].u);
    int fv = find(e[now].v);
    if (fu != fv) { // 加入该边不构成环
        p[fu] = fv;
        dfs(x, now + 1, k + 1); // 选该边
        p[fu] = fu; // 回溯
    }
    dfs(x, now + 1, k); // 不选该边
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) p[i] = i;
    for (int i = 1; i <= m; i++) {
        int a, b, c; cin >> a >> b >> c;
        e[i] = {a, b, c};
    }
    sort(e + 1, e + 1 + m);

    int tot = 0; // 生成树中边的数量
    for (int i = 1; i <= m; i++) {
        if (e[i].w != e[i - 1].w) {
            num++;
            ed[num].l = i;
            ed[num - 1].r = i - 1;
        }

        int fu = find(e[i].u);
        int fv = find(e[i].v);
        if (fu != fv) {
            p[fu] = fv;
            ed[num].cnt++;
            tot++;
        }
    }

    if (tot != n - 1) {
        cout << 0 << endl;
        return 0;
    }

    ed[num].r = m;
    ans = 1;
    for (int i = 1; i <= n; i++) p[i] = i;
    for (int i = 1; i <= num; i++) {
        cnt = 0;
        dfs(i, ed[i].l, 0);
        ans = (ans * cnt) % MOD;
        for (int j = ed[i].l; j <= ed[i].r; j++) {
            int fu = find(e[j].u);
            int fv = find(e[j].v);
            if (fu != fv) p[fu] = fv;
        }
    }
    cout << ans << endl;

    return 0;
}

问题描述 ​

分析 ​

参考代码 ​

问题描述

分析

参考代码