2024.8.17

130124202408171002

DATE #:20240817

ITEM #:DOC

WEEK #:SATURDAY

DAIL #:捌月拾肆

TAGS

	
< BGM = "快哉风 -- 黄金玉米王" >
< theme = oi-language >
< theme = oi-graph theory >
< [空] > 
< [空] >

取次花丛懒回顾，半缘修道半缘君 -- 元稹《离思五首·其四》

[P4208 [JSOI2008] 最小生成树计数]([P4208 JSOI2008] 最小生成树计数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

[JSOI2008] 最小生成树计数

题目描述

现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两棵最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生成树可能很多，所以你只需要输出方案数对 $31011$ 的模就可以了。

输入格式

第一行包含两个数，$n$ 和 $m$，其中 $1\le n\le 100$，$1\le m\le 1000$，表示该无向图的节点数和边数。每个节点用 $1\sim n$ 的整数编号。

接下来的 $m$ 行，每行包含两个整数：$a,b,c$，表示节点 $a,b$ 之间的边的权值为 $c$，其中 $1\le c\le 10^9$。

数据保证不会出现自回边和重边。注意：具有相同权值的边不会超过 $10$ 条。

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

8

提示

数据范围及约定

对于全部数据，$1\le n\le 100$，$1\le m\le 1000$，$1\le c_i\le 10^9$。

先引入一个引理：

对于一个图的最小生成树，每个边权的边出现的次数是一样的

证明：模拟kruskal的过程，我们在给边排序时，交换同权的边并没有什么影响

那么我们先求解出最小生成树，并依次计算权值

考虑，当我们要加入权值为$i$的若干条边时，

前面加入的边已经使其变成了几个联通块，只要考虑用权值为$i$的边跑一次生成树数量即可，

之后对每个边权都依次操作

    
    //2024.8.17
    //by white_ice
    //[JSOI2008] 最小生成树计数 |P4208
    #include