Responsive image

问题 D: 最小生成树计数

问题 D: 最小生成树计数

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

现在给出了一个简单无向加权图。

你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。

如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的。

输入描述

第一行包含两个整数 n 和 m，表示该无向图的节点数和边数，节点用 1~n 编号。
接下来 m 行，每行包含三个整数 a,b,c，表示节点 a 和节点 b 之间存在一条边，权值为 c。

输出描述

输出不同的最小生成树有多少个。
你只需要输出数量对 31011 的模就可以了。

样例输入

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

样例输出

8

提示

1≤n≤100,

1≤m≤1000,

1≤c≤1000000000,

数据保证不会出现自回边和重边。

具有相同权值的边不会超过 10 条

[提交][状态]
ACM算法攻关部