题目分析

计算无向加权图中不同最小生成树的数量，结果对 $31011$ 取模。

算法思路：Kruskal + 按权值分组枚举

关键观察

• 最小生成树中，相同权值的边选择方案独立
• 对于每种权值，在不形成环的前提下枚举边选择方案
• 总方案数 = 各权值对应方案数的乘积

核心步骤

1. 边排序与分组

sort(e + 1, e + 1 + m, cmp);  // 按边权升序排序
for(int i=1; i<=m; i++)
    if(e[i].w != e[i+1].w)
        res = res * sol(lp+1, i) % mod, lp = i;  // 处理相同权值边组

2. 相同权值边方案计算

int sol(int l, int r) {
    // 枚举所有边选择组合 (2^(r-l+1) 种)
    for(int S=0; S<(1<<(r-l+1)); S++) {
        // 检查选择边集是否形成环
        // 统计最大边数方案
    }
    // 实际添加边到最小生成树
    for(int i=l; i<=r; i++)
        t += mg(e[i].u, e[i].v);
    return tr;  // 返回方案数
}

3. 并查集维护连通性

• f[]: 主并查集，记录实际连通性
• g[]: 临时并查集，用于检查环

数学原理

设最小生成树总权值为 $W$，对于权值 $w$ 的边组：

• 必须选择恰好能连通当前连通分量的最大边数
• 不同权值边组的选择相互独立
• 总方案数 = $\prod_{w} \text{count}(w)$

其中 $\text{count}(w)$ 是权值 $w$ 边组的有效选择方案数。

复杂度分析

• 边分组：$O(m \log m)$ 排序
• 方案枚举：每组最多 $10$ 条边，$O(2^{10})$ 枚举
• 并查集操作：$O(n\alpha(n))$
• 总复杂度：$O(\frac{m}{10} \cdot 2^{10} \cdot n\alpha(n))$，在数据范围内可行

样例验证

输入：

4 6
1 2 1
1 3 1  
1 4 1
2 3 2
2 4 1
3 4 1

处理过程：

• 权值 $1$ 的边：$4$ 条边，$8$ 种选择方案
• 权值 $2$ 的边：$1$ 条边，$1$ 种选择方案
• 总方案数：$8 \times 1 = 8$

输出：8，与样例一致。

算法优势

• 利用边数限制：相同权值边不超过 $10$ 条，使枚举可行
• 分组独立计算：简化问题复杂度
• 正确性保证：基于最小生成树性质

该解法通过权值分组和状态枚举，高效计算了不同最小生成树的数量。