题目大意:
给你一个全连接的图, 边权为 1-k, 然你构造出一个, 图 使得 1到其他节点的菊花图,为最小生成树. 问有多少种
思路:
- 先考虑如何构造. 反向思考, 此时这个菊花图是一个最下生成树, 如何让他不是, 那么就是 某个点到其他点的权值比他到1号点的权值小,
- 所以就是那个啥.
- 如何计算种类数? 利用dp
- 下面是大佬 dp转移 好好学学!! (洛谷题解)
后记:
- 在思考如何dp时,就先想最笨的那种,把信息都表示出来,在多弄几个循环,最后在来优化
标签：star,MST,菊花,如何,权值,dp From： https://www.cnblogs.com/Lamboofhome/p/16789489.html