[POJ 1639]

Picnic Planning

度限制最小生成树

给出最多包含最多21个结点的无向图,边权值为正数,求这样的一棵最小生成树:与结点1相连的树边不超过m条。

解法是,先从图中剔除结点1,求最小生成森林。然后重复:遍历结点1相连的所有边,找(1)能联通某森林的最小边;(2)若(1)边不存在,则找加边之后作破圈操作能使树权减少最多的边。直到m次加边机会耗尽或者加边也无法减少树权。

一些小技巧:题目数据量很小,所以邻接矩阵也可以,但如果像我这样习惯用邻接表的话,对树边作标记的时候两个方向的边要同时标记。而由于加边时无向边对应的邻接表项是成对插入的,也即编号仅有最末位不同,所以^1就可以得到另一个方向的边了。这种用邻接表时修改边信息的做法很常用,最开始是在做费用流的题目时学到的。