108e专题

CF 108E Garden(DP,斯坦纳树)

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