做题网站推荐: OpenJudge VIJOS CF JOYOI 洛谷 RQNOJ POJ HDU 牛客网 计蒜客 图论工具
本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 签到 网课签到
输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载 实名认证 卡评测举报
原题来自:JSOI 2008
现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树,而希望知道这个图中有多少个不同的最小生成树。(如果两颗最小生成树中至少有一条边不同,则这两个最小生成树就是不同的)。
第一行包含两个数,nnn 和 mmm,表示该无向图的节点数和边数,每个节点用 1∼n1sim n1∼n 的整数编号;接下来的 mmm 行,每行包含两个整数:a,b,ca,b,ca,b,c,表示节点 a,ba,ba,b 之间的边的权值为 ccc。
输出不同的最小生成树有多少个。你只需要输出数量对 310113101131011 的模就可以了。
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≤1091le nle 100,1le mle 1000,1le cle 10^91≤n≤100,1≤m≤1000,1≤c≤109。
数据保证不会出现自回边和重边。
注意:具有相同权值的边不会超过 101010 条。
一本通提高篇 10070 JSOI 早于2010 矩阵树定理 最小生成树 数学