题解 P2143 【[JSOI2010]巨额奖金】
Night_Aurora · · 题解
对此我们先求一遍最小生成树，如果无法生成树就输出0
然后记录最小生成树上的每个权值的边有几条
对于权值为W的边，最小生成树上有k条
那么把这些边从最小生成树上去掉，会形成编号为
那么在所有边权为W的边中选k条，只要能把这k+1个连通块连起来，就是这个权值的一个方案
根据乘法原理，总方案数就是上面所有权值的乘积
试着证明一下正确性
在原最小生成树中，权值为W的k条边的唯一作用就是把
而我们换另外k条边的一个组合，只要能连通这些k+1个连通块，在生成树中的作用就等价于原来k条边，所以可以证明计算出的最小生成树个数一定分别对应一种真实存在的最小生成树
反过来，对于一个最小生成树，假设它没有被计数，那有两种可能性
一种是某种权值的边个数与原最小生成树不一样，那可以证明这两个生成树一定至少有一个不是最优的，与前面矛盾
另一种是某个权值的边未能连通原k+1个连通块，不算重边的话，一定有一条边的两个端点都在原一个连通块里，因为原最小生成树是最优的，所以可证明这种情况不成立
从而反证出没有合法的最小生成树没有被计数
计数就是最小生成树个数得证
唠叨这么长了，代码就不贴了，贴个链接吧
没有注释的代码