[JSOI2008] 最小生成树计数
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
[AdditionalFile2622.zip](file://AdditionalFile2622.zip?type=additional_file)
#2622. 「JSOI2008」最小生成树计数
标签: 传统 | 时间限制: 1000 ms | 内存限制: 125 MiB |
题目描述
现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生成树可能很多，所以你只需要输出方案数对 的模就可以了。
输入格式
第一行包含两个数， 和 表示该无向图的节点数和边数。每个节点用 的整数编号。
接下来的 行，每行包含两个整数：，表示节点 之间的边的权值为 。
数据保证不会出现自回边和重边。注意：具有相同权值的边不会超过 条。
输出格式
输出不同的最小生成树有多少个。你只需要输出数量对 的模就可以了。
样例
输入
4 6
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1
输出
8
数据范围与提示
对于 的数据，，，。
提高8.16-18（并查集+最小生成树）
- 状态
- 已结束
- 规则
- XCPC
- 题目
- 17
- 开始于
- 2024-8-1 22:00
- 结束于
- 2024-8-20 2:00
- 持续时间
- 436 小时
- 主持人
-
admin
- 参赛人数
- 14