Reach-Top OJ

问题 2173 --最小生成树计数

2173: 最小生成树计数★★★★

时间限制: 1 Sec 内存限制: 128 MB
提交: 30 解决: 22
[提交][状态][命题人:]

现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。

第一行包含两个数，

n

和

m

，表示该无向图的节点数和边数，每个节点用

1∼n1\sim n

的整数编号；
接下来的

m

行，每行包含两个整数：

a, b, c

，表示节点

a, b

之间的边的权值为

c

。

输出不同的最小生成树有多少个。你只需要输出数量对

31011

的模就可以了。

样例输入

Copy

样例输出

Copy

对于全部数据， $1≤n≤100,1≤m≤1000,1≤c≤1091\le n\le 100,1\le m\le 1000,1\le c\le 10^9$ 。

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

注意：具有相同权值的边不会超过 $10$ 条。