[USACO11DEC]Simplifying the Farm G

By xiaruize

题面

求一张竞赛图中最小生成树的方案数

思路

Kruskal求最小生成树，记录每个长度的边被选择几次

重新跑Kruskal,对于长度一样的边，dfs检查有多少选法，使结果仍然是最小生成树，乘法原理求结果

例如，在这张图中，对于长度为1的边，本来选定2条，所以只有一种方案

对于长度为2的边，本来选定1条，dfs检查其它长度为2的边，均可以，答案 ×3\times 3

Code