题目大意
给定一棵 $n$ 个点的目标树,以及 $m$ 棵模板树,每棵模板树有一个单价 $c_i$,数量无限多。这里的树都是无根树。
现在要用若干模板树拼成目标树(就是用模板去覆盖目标树,使得目标树的每个点恰好被覆盖一次),求最小代价。
$n \leq 500,\ m \leq 200$,所有模板树的结点数总和 $N \le 500$
$c_i \leq 10^6$
1s
题解
妙啊。。。
首先大的框架是个树形 dp。把目标树当有根树,设 $dp_{i,(j,pj)}$ 表示目标树的第 $i$ 个结点,匹配模板里的结点 $j$,$i$ 连向父亲的边匹配 $j$ 连向 $pj$ 的边,的最小代价;设 $g_i$ 表示目标树以 $i$ 为根的子树完全匹配的最小代价。
$dp$ 数组的状态数是 $O(nN)$ 的。$g_i$ 也可以视为 $\min_{j} dp_{i,(j,0)}$($0$ 就表示 $j$ 没有父亲,是所在其模板树的根),所以以下就是求 $dp$ 数组。
而这个转移就是让 $i$ 的儿子去匹配 $j$ 的儿子。这是一个二分图最小权匹配:左边一排 $deg_j-1$ 个点表示模板树上 $j$ 的儿子(如果是在做 $dp_{i,(j,0)}$,那么 $j$ 没有父亲,左边就有 $deg_j$ 个点),右边一排 $deg_i-1$ 个点表示目标树上 $i$ 的儿子,左边 $x$ 连向右边 $y$ 的边权是 $dp_{y,(x,j)}-g_y$,最后答案加上 $\sum g_y$。
注意到只有 $j$ 的儿子数 $\le i$ 的儿子数才有意义,因此这样一次 KM 的时间复杂度是 $O(deg_j^2 \cdot deg_i)$,如果每一对 $(i,j,pj)$ 都做一次 KM 的话,时间复杂度是
T 掉了。
所以这里加一个改进,观察到,$dp_{i,(j,pj)}$ 的二分图匹配,实际上就是 $dp_{i,(j,0)}$ 的二分图匹配删去左边 $pj$ 这个点。既然如此,就没必要重新跑一边 KM,直接用最短路退流就好了。
具体来说,首先做出 $dp_{i,(j,0)}$ 的 KM,答案为 $ans$,然后求出左边每个点走交错路到达右边结点的最短路(从左到右只能退流匹配边,从右到左只能走非匹配边),记为 $aug_{pj}$,那么 $dp_{i,(j,pj)}=ans+aug_{pj}$。这个最短路用 floyd 就好了。
来分析时间复杂度。KM 的部分现在是
floyd 的部分需要注意姿势,如果直接对 $deg_i+deg_j$ 个点跑最短路,或者对右边的 $deg_i$ 个点跑最短路,时间都是不对的:
要对左边的点跑 floyd,用到的性质是“左边的点数 $\le$ 右边的点数”,因此时间复杂度是
具体来说,对于左边的两点 $x,y$,设它们的 KM 匹配点分别为 $x’,y’$,二分图从 $i$ 到 $j$ 的边权为 $w_{i,j}$,那么在 floyd 的初始距离中,$x$ 到 $y$ 的距离为 $-w_{x,x’}+w_{y,x’}$。这样求出最短路以后,退流 $x$ 的答案为 $aug_x=\min_{y} dis_{x,y}-w_{y,y’}$ 。
注意一个细节,如果 $j$ 的儿子数比 $i$ 多 1 个(即 $deg_j=deg_i-1+1=deg_i$),那么 $dp_{i,(j,0)}$ 的 KM 是不合法的,但 $dp_{i,(j,pj)}$ 的 KM 都是合法的。这里可以给右边加一个空点,跑 $dp_{i,(j,0)}$ 的 KM 但不要更新答案,然后退流的时候,强制 floyd 的终点是右边这个空点。
代码
// 这里的 KM 跑的是二分图最大权匹配,所以边权取反,floyd 跑最长路
1 |
|