网站首页
编程语言
数据库
系统相关
其他分享
编程问答
P6192
2024-12-06
P6192 【模板】最小斯坦纳树
题目描述:题目给定一张图上的几个关键点,要求我们用最小的边权将这些点连起来不难发现,最后连出来的答案一定是一棵树:如果有环的话,将环优化掉一定更好我们考虑dp:对于一个节点x钦定它是这颗树的根。记dp[rt][s]表示以rt为根,关键点被链接的状态为s时的最小花费则在最短路中