破坏一个棵树的,就是把他的所有边都删掉,现在有两种方式就是删掉i点的所有入边,还有就是删掉i点的所有出边,所需要的费用为Wi+,Wi-,每一条边<u,v>要被销掉,要么删除u的所有出边,要么删除v的所有入边,每条边都至少与一种操作相关联,我们可以联想到二分图的最小点集覆盖,求最小的点集,让所有的边都与之关联。对于这个题来说就是典型的模型了。二分图的最小点权覆盖,AMBER的论文第30页有讲,不再赘述,注意不要把边权选错了,入度的权在右边。。。我因为这个搞了一个下午。
还有,我的最大流模板已经十分完善了,就在blog上放我的模板,以后会填上费用流,强连通等的并且不断改进: