Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom2年前

03/8
19:30
dfs

[bzoj 1016] JSOI2008 最小生成树计数

00:00/00:00

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行包含两个数,n和m,其中1<=n<=100; 1<=m<=1000; 表示该无向图的节点数和边数。每个节点用1~n的整数编号。接下来的m行,每行包含两个整数:a, b, c,表示节点a, b之间的边的权值为c,其中1<=c<=1,000,000,000。数据保证不会出现自回边和重边。注意:具有相同权值的边不会超过10条。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

8

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

最小生成树计数可以直接用matrix tree定理

但是我们发现题目中有这样一句话:“注意:具有相同权值的边不会超过10条。” 所以直接搜索就行了。

有这两个定理:最小生成树中每个权值的边的数量是固定的,且从小到大选取相同权值的边之后连通性也是确定的,所以就可以先求出最小生成树,然后对每条权值相同边的使用情况分别搜索,最后乘法原理。

c++:

pascal:

 

[bzoj 1016] JSOI2008 最小生成树计数