首页 > 代码库 > 2014.12.12 生成树

2014.12.12 生成树

只是简单地写一下关于晚上看的,次小生成树和最小k限制生成树,似乎都挺简单的(但是代码yy了下还是挺难写的)。次小生成树:首先它一定是最小生成树的一个邻集(就是两棵树就只有两条边不一样啦),然后先求出最小生成树,再不断去枚举选取哪条剩下的边,加入这条边后最小生成树就带有一个环,求出环中权值最大的边,去掉就是选取这条边所能达到的生成树的最小方案了,然后枚举很多条边发现有很多重复操作,所以先dp处理出来……而最小k限制生成树似乎也是一样,就把那个特殊的点先拿出来,然后其他的跑最小生成树,如果这时候跑出的最小生成树个数大于限制k,显然不存在满足要求的树,否则就全部连起来,得到一个特殊点度问m的生成树。由于限制m+1的生成树是限制m的生成树的一个邻集,然后就暴力从m推到k……中间同样可以用dp优化下。然后就没了……&(然后还是不会写啊)

2014.12.12 生成树