现在给出了一个简单无向加权图。
你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。
如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的。
问题 D: 最小生成树计数
时间限制: 1 Sec 内存限制: 128 MB提交: 0 解决: 0
[提交][状态][讨论版][命题人:]
题目描述
输入描述
第一行包含两个整数 n 和 m，表示该无向图的节点数和边数，节点用 1~n 编号。
接下来 m 行，每行包含三个整数 a,b,c，表示节点 a 和节点 b 之间存在一条边，权值为 c。
接下来 m 行，每行包含三个整数 a,b,c，表示节点 a 和节点 b 之间存在一条边，权值为 c。
输出描述
输出不同的最小生成树有多少个。
你只需要输出数量对 31011 的模就可以了。
你只需要输出数量对 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 条
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
关于网站改版