「一本通 3.1 练习 5」最小生成树计数

形式化题目

给定一个含 $n$ 个顶点、 $m$ 条边的无向连通简单图，边权为正整数。定义两个生成树不同当且仅当它们所包含的边集不同。

求该图的最小生成树（MST）总数，结果对 $31011$ 取模。

数据保证相同权值的边数不超过 $10$ 条。

正解

思路

1. 最小生成树的核心性质

对于任意无向带权图，所有可能的最小生成树都满足以下两条基本性质：

各权值边数唯一性：不同最小生成树中，各个权值 $w$ 所包含的边数 $c_w$ 是恒定且唯一的，与 Kruskal 算法求出的一棵生成树中该权值的边数完全相同。
连通分量等价性（收缩性质）：处理完所有权值严格小于 $w$ 的边之后，图中的点所构成的连通块（连通分量）划分是唯一确定的，与前面权值具体选择了哪一组树边完全无关。

由上述性质可知，各个不同权值段的选边方案相互独立。整张图的最小生成树方案数即为各权值段选边方案数的乘积（乘法原理）：

\text{Ans} = \prod_{w} (\text{权值为 } w \text{ 的边中选取 } c_w \text{ 条且不产生环的方案数}) \pmod{31011}

2. 结合题目约束进行组合枚举

题目给出了一个极强的特殊性质：相同权值的边不超过 $10$ 条。

设某个权值段共有 $k$ 条边，Kruskal 探测出需要选取 $c_w$ 条边，则满足 $c_w \leqslant k \leqslant 10$ 。从 $k$ 条边中挑选 $c_w$ 条边的所有可能组合至多为：

\binom{10}{5} = 252

由于数量极小，我们完全可以直接枚举该权值段所有大小为 $c_w$ 的子集：

在当前的连通状态下，检查所选的 $c_w$ 条边是否会在连通块之间构成环。
若无环，则该组合是一个合法的生成森林方案，计数加 $1$ 。

3. 算法全流程

第一阶段（Kruskal 探测）：
- 将所有边按边权升序排序。
- 运行标准 Kruskal 算法，按权值分段。记录每个权值段的所有候选边集合 $E_w$ ，以及该段实际并入生成树的边数 $c_w$ 。
- 若最终加入生成树的总边数小于 $n - 1$ ，说明原图不连通，无最小生成树，直接输出 $0$ 。
第二阶段（按段独立枚举）：
- 重新维护一个工作并查集。
- 依次遍历每个权值段 $(E_w, c_w)$ ：
  - 若 $c_w = 0$ ，对答案贡献的倍率为 $1$ ，直接跳过。
  - 过滤掉两端点已在当前并查集中属于同一连通块的边。
  - 用组合枚举（combinations）在该段剩余边中选出 $c_w$ 条边，利用临时并查集验证是否成环，累加合法方案数 $\text{ways}$ 。
  - 答案累乘： $\text{ans} \gets (\text{ans} \times \text{ways}) \bmod 31011$ 。
  - 处理完毕后，在工作并查集中将 $E_w$ 中端点所属的不同连通块真实合并。
输出：输出累计的 $\text{ans}$ 。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 14:27
# update_at: 2026-09-30 14:27

import sys
from itertools import combinations

MOD = 31011


def find(parent: list[int], u: int) -> int:
    """查带路径压缩的并查集代表元。"""
    while parent[u] != u:
        parent[u] = parent[parent[u]]
        u = parent[u]
    return u


def count_valid_subsets(edges: list[tuple[int, int]], need: int, base_parent: list[int]) -> int:
    """在同权边集中暴力选择 need 条边，统计能形成无环森林的方案数。"""
    if need == 0:
        return 1

    valid_count = 0
    for chosen in combinations(edges, need):
        parent = list(base_parent)
        cycle_found = False
        for u, v in chosen:
            ru = find(parent, u)
            rv = find(parent, v)
            if ru == rv:
                cycle_found = True
                break
            parent[ru] = rv
        if not cycle_found:
            valid_count += 1
    return valid_count


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    tokens = list(data)
    if not tokens:
        return
    it = iter(tokens)
    n = next(it)
    m = next(it)

    raw_edges = [(next(it), next(it), next(it)) for _ in range(m)]
    raw_edges.sort(key=lambda e: e[2])

    # 第一阶段：Kruskal 探测各权值段在生成树中必须贡献的边数
    parent = list(range(n + 1))
    groups: list[tuple[list[tuple[int, int]], int]] = []  # (当前权值的边集, 需选取的边数)
    total_edges = 0

    idx = 0
    while idx < m:
        weight = raw_edges[idx][2]
        group_edges: list[tuple[int, int]] = []
        chosen_in_group = 0

        while idx < m and raw_edges[idx][2] == weight:
            u, v, _ = raw_edges[idx]
            group_edges.append((u, v))
            ru = find(parent, u)
            rv = find(parent, v)
            if ru != rv:
                parent[ru] = rv
                chosen_in_group += 1
                total_edges += 1
            idx += 1

        if chosen_in_group > 0:
            groups.append((group_edges, chosen_in_group))

    # 图不连通无法构成最小生成树
    if total_edges < n - 1:
        print(0)
        return

    # 第二阶段：按权值段独立统计选取方案数并累乘
    work_parent = list(range(n + 1))
    ans = 1

    for edges, need in groups:
        # 将边端点映射为当前连通分量代表元
        mapped_edges = [(find(work_parent, u), find(work_parent, v)) for u, v in edges]
        filtered_edges = [(u, v) for u, v in mapped_edges if u != v]

        ways = count_valid_subsets(filtered_edges, need, work_parent)
        ans = (ans * ways) % MOD

        # 将该权值段在并查集中真实合并（任意一种无环选取方案产生的连通性一致）
        for u, v in edges:
            ru = find(work_parent, u)
            rv = find(work_parent, v)
            if ru != rv:
                work_parent[ru] = rv

    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 04:10
 * update_at: 2026-10-05 04:10
 */

// 最小生成树计数（JSOI 2008）：同权边不超过 10 条，按权值段枚举选边方案。
// 性质 1：所有 MST 中权值为 w 的边数 c_w 固定，等于 Kruskal 求出的数量。
// 性质 2：处理完所有权值 < w 的边后，连通块划分唯一，与具体选法无关。
// 所以各权值段选边方案相互独立，答案 = 各段合法选法数的乘积，对 31011 取模。

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 105;   // 顶点数上限
const int MAXM = 1005;  // 边数上限
const ll MOD = 31011;   // 题目要求的模数

int n, m;

// 边结构：按权值排序后按段处理
struct Edge {
    int u;
    int v;
    ll w;
};
Edge edges[MAXM];

ll fa[MAXN];  // 并查集父节点（第一阶段探测、第二阶段合并时各初始化一次）

ll find_fa(ll x) {
    while (fa[x] != x) x = fa[x];
    return x;
}

// 每个权值段的记录：need[i] = 第 i 段在 MST 中必须选的边数（0 的段不计入）
int seg_start[MAXM];  // 段在排序后边数组中的起始下标
int seg_len[MAXM];    // 段内边数
int seg_need[MAXM];   // 该段必须选的边数
int seg_total = 0;    // need > 0 的段数

// 第二阶段：当前段映射到连通块代表元后的可选边
int cur_u[MAXM];
int cur_v[MAXM];
int cur_cnt;

// 枚举状态
int need;         // 当前段需要选的边数
int way_cnt;      // 当前段的合法方案数
ll tmp_fa[MAXN];  // 验证单个组合时的临时并查集
int sel_u[12];    // 当前已选边的端点（need <= 10）
int sel_v[12];

ll tmp_find(ll x) {
    while (tmp_fa[x] != x) x = tmp_fa[x];
    return x;
}

// 递归枚举：第 dep 层对第 dep 条可选拍边做"选 / 不选"的决定，
// 凑满 need 条后用临时并查集检查是否无环，无环则方案数 +1。
void dfs_choose(int dep, int chosen) {
    // 剪枝：剩下的边不够凑满 need 条
    if (chosen + (cur_cnt - dep) < need) return;
    if (chosen == need) {
        // 完整方案已生成：复制工作并查集后验证无环
        for (int i = 1; i <= n; i++) tmp_fa[i] = fa[i];
        for (int i = 0; i < need; i++) {
            ll ru = tmp_find(sel_u[i]);
            ll rv = tmp_find(sel_v[i]);
            if (ru == rv) return;  // 有环，非法
            tmp_fa[ru] = rv;
        }
        way_cnt++;
        return;
    }
    if (dep >= cur_cnt) return;

    // 不选第 dep 条边
    dfs_choose(dep + 1, chosen);

    // 选第 dep 条边（存端点便于叶子统一验证）
    sel_u[chosen] = cur_u[dep];
    sel_v[chosen] = cur_v[dep];
    dfs_choose(dep + 1, chosen + 1);
}

bool cmp_edge(const Edge &a, const Edge &b) {
    return a.w < b.w;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d %d %lld", &edges[i].u, &edges[i].v, &edges[i].w);
    }
    sort(edges, edges + m, cmp_edge);

    // ===== 第一阶段：Kruskal 探测每个权值段必须选的边数 =====
    for (int i = 1; i <= n; i++) fa[i] = i;
    int total_used = 0;  // 加入生成树的总边数
    int idx = 0;
    while (idx < m) {
        int start = idx;
        int cnt_need = 0;
        while (idx < m && edges[idx].w == edges[start].w) {
            ll ru = find_fa(edges[idx].u);
            ll rv = find_fa(edges[idx].v);
            if (ru != rv) {  // 不连通则这条边属于这棵 MST
                fa[ru] = rv;
                cnt_need++;
                total_used++;
            }
            idx++;
        }
        if (cnt_need > 0) {  // 记录 need > 0 的段
            seg_start[seg_total] = start;
            seg_len[seg_total] = idx - start;
            seg_need[seg_total] = cnt_need;
            seg_total++;
        }
    }

    // 图不连通，不存在生成树
    if (total_used < n - 1) {
        printf("0\n");
        return 0;
    }

    // ===== 第二阶段：按段独立枚举选法数并累乘（fa 重新初始化为工作并查集）=====
    for (int i = 1; i <= n; i++) fa[i] = i;
    ll ans = 1;
    for (int s = 0; s < seg_total; s++) {
        // 过滤：端点已在同一连通块的边映射后相同，必不可选
        cur_cnt = 0;
        for (int i = 0; i < seg_len[s]; i++) {
            Edge &e = edges[seg_start[s] + i];
            ll ru = find_fa(e.u);
            ll rv = find_fa(e.v);
            if (ru != rv) {
                cur_u[cur_cnt] = ru;
                cur_v[cur_cnt] = rv;
                cur_cnt++;
            }
        }
        need = seg_need[s];
        way_cnt = 0;
        dfs_choose(0, 0);
        ans = (ans * way_cnt) % MOD;

        // 真实合并这一段：任意一种合法选法产生的连通性一致（性质 2）
        for (int i = 0; i < seg_len[s]; i++) {
            Edge &e = edges[seg_start[s] + i];
            ll ru = find_fa(e.u);
            ll rv = find_fa(e.v);
            if (ru != rv) fa[ru] = rv;
        }
    }

    printf("%lld\n", ans);
    return 0;
}

复杂度

时间复杂度： $O(m \log m + \sum \binom{k_i}{c_i} \cdot c_i \cdot \alpha(n))$ 。其中 $m \leqslant 1000$ ， $n \leqslant 100$ ，每个权值段边数 $k_i \leqslant 10$ ，组合数 $\binom{k_i}{c_i} \leqslant 252$ 。总运算次数在 $10^6$ 量级以内，在 Python 中可在 $0.02\text{ s}$ 内全部秒过。
空间复杂度： $O(n + m)$ ，维护边表与并查集数组，空间开销远小于 $128\text{ MB}$ 。

总结

最小生成树计数问题通常需借助 Matrix-Tree 定理（矩阵树定理）求解，但在本题中，限制条件“相同权值的边不超过 $10$ 条”大大降低了难度，使得我们能通过 Kruskal 性质分解权值段，再利用简单的子集枚举独立求解各段方案数。

图示解析

下图展示了算法按权值分段处理与连通性传递的解题流程：

flowchart TD
    A[所有边按权值升序排序] --> B[第一遍 Kruskal 算法]
    B --> C{总边数是否为 n-1?}
    C -- 否 --> D[输出 0 图不连通]
    C -- 是 --> E[记录每个权值段所需边数 c_w]
    E --> F[按权值从小到大遍历各个权值段]
    F --> G[在当前缩点基础上枚举 c_w 条边的子集]
    G --> H[统计该段不形成环的方案数 ways]
    H --> I[ans = ans * ways mod 31011]
    I --> J[在工作并查集中真实合并这批连通块]
    J --> K{还有下一个权值段?}
    K -- 是 --> F
    K -- 否 --> L[输出最终计数 ans]