问题 给出一张正权联通图和K个点，求连接这K个点的连通块最小权值和 题解 首先可以确定答案连通块是一棵树，因为如果有环则删去环上任意一条边就更优 引入斯坦纳树 设f[i][s]为以i为根的树达到这K个点为s的状态所需的最小权值和 有（t|s=s）时，f[i][s]=min(f[i][s],f[i][t]+f[i][s-t]) 有i与j有边时，f[i][s]=min(f[i][s],f[j][s

题意：有n个星球，其中有些星球上有多个工作，有些星球上有些资源（但是一个星球上的资源只能提供给一个工厂），知道在一些星球边建立边的代价，问使得得到资源的工厂的数目最多的多少，在些前提下代价最小是多少。 还是斯坦纳树，不懂看：http://endlesscount.blog.163.com/blog/static/821197872012525113427573/ #include <iost

题意：给你n,m,k ，分别表示有n个点，m条边，每条边有一个权值，表示修复这条边需要的代价，从前k个点中任取一个使其和后k个点中的某一个点，通过边连接，并且必须是一一对应，问最小的代价是多少。     同样是斯坦纳树，不过最后得到的答案可能是森林，所以最后要跑一个DP。如果不懂斯坦纳树，看：http://endlesscount.blog.163.com/blog/static/82119

题意：给你一个n*m的矩阵，和k个点，要求使这k个点相互连接，并且使连接的代价最小（每个矩阵上都有一个权值，如果权值为0表示k个点其中的一个，连接的代价等于将这些点连接起来的路径上的权值和。）    简单的斯坦纳树，只要要要多开一个数组记录路径。如果不懂斯坦纳树，看http://endlesscount.blog.163.com/blog/static/821197872012525113427

Description 小铭铭最近进入了某情报部门，该部门正在被如何建立安全的通道连接困扰。 该部门有 n 个情报站，用 1 到 n 的整数编号。给出 m 对情报站 ui;vi 和费用 wi，表示情 报站 ui 和 vi 之间可以花费 wi 单位资源建立通道。 如果一个情报站经过若干个建立好的通道可以到达另外一个情报站，那么这两个情报站就 建立了通道连接。形式化地，若 ui 和 vi 建立了通

斯坦纳树解决的是这么一类问题——在图上选择N个节点，求只计算这N个节点的最小生成树。该问题是NP完全的，这意味着它没有多项式时间的解法。一般来说，我们使用状压DP解决这个问题        我们让   表示已经考虑的节点状态为i（如果i的第k位是1，那么我们已经把需要考虑的第k个节点考虑进去了），当前斯坦纳树的根节点为j的解（边权和），那么，显然一棵斯坦纳树可以裂成两个，换句话说

考虑著名的Steiner Tree问题： 问题描述 设 G （ V , E , W ）是一个无向带权连通图 ( V 是顶点的集合， E 是边的集合， W 是边上权重的集合，顶点 v i , v j ∈ V ，由 v i , v j 构成的边记为 e i j 或者 e j i , 边上的权重记为 w i j 或者 w j i , 且 w i j = w j i , w i j > 0 ) 。