本文从WordPress迁移而来, 查看全部WordPress迁移文章
最小树型图这个内容其实有点鸡肋,用得不多,能找到的题目多时模板题,题目都是要求输出最小树形图的总权和,并没有要求输出最小树形图的具体形状,如果真要输出输出完整的最小树形图,应该要改掉整个代码实现,在这个方面没有深究
最小树形图模板——来自小HH
1 | int Directed_MST(int root,int nv,int ne){ |
下面是几道题目,可以说都是模板题
- uva 11183 Teen Girl Squad,纯模板
- poj 3164 Command Network,纯模板
- hdu 3072 Intelligence System ,这题求完强连通分量后保证是一个DAG了,所以不会有环,直接找到每个点的最小入边就能构成最小树形图
- hdu 4009 Transfer water,一个定根的最小树形图,不过为了解决两种可能需要添加虚根,在模板题上稍有变化
- hdu 2121 Ice_cream’s world II,无定根的最小树形图,添加虚根