2026 CSP-S 模拟卷（一）T2 生成树计数

题目背景与题意

某地区的规划图可以看成一个 $n$ 个点、$m$ 条边的无向连通图，第 $i$ 条边连接 $u_i$ 与 $v_i$，造价为 $w_i$。政府希望用最少的造价让所有点连通，也就是选出若干条边构成一棵生成树，使总造价最小。

现在要统计：总造价最小的生成树一共有多少棵（两棵生成树视为不同，当且仅当它们选出的边集不同）。由于答案可能很大，请输出它对 $10^9+7$ 取模的结果。如果图本身不连通，输出 0。

输入格式

第一行两个整数 $n, m$。

接下来 $m$ 行，每行三个整数 $u_i, v_i, w_i$。

输出格式

一行一个整数，表示最小生成树的个数对 1000000007 取模的结果。

样例输入

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

样例输出

2

样例解释

用权为 1 的两条边 $(1,2)$ 与 $(3,4)$ 把图分成两个连通块 $\{1,2\}$ 与 $\{3,4\}$。接下来必须再选一条权为 2 的边把两块连起来，可选 $(1,3)$ 或 $(2,4)$，各得到一棵生成树，总造价都是 $1+1+2=4$。权为 3 和 5 的边出现在任何生成树里都会让总造价超过 4，所以都不是最小生成树。因此最小生成树共 2 棵。

数据范围与子任务

对全部数据：$1 \le n \le 400$，$0 \le m \le 1000$，$1 \le w_i \le 10^9$，图保证连通（子任务 1 的图可能不连通，用于检验输出 0 的情况），答案对 $1000000007$ 取模。

子任务采用捆绑测试：子任务内部的测试点必须全部通过才能拿到该子任务的全部分值，否则该子任务得 0 分。

时间限制 1 秒，空间限制 512 MB。