#P2465. [SDOI2008] 山贼集团

    ID: 1473 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp2008各省省选山东O2优化枚举暴力状态压缩状压

[SDOI2008] 山贼集团

题目描述

某山贼集团在绿荫村拥有强大的势力。整个绿荫村由 nn 个连通的小村落组成,并且保证对于每两个小村落有且仅有一条简单路径相连。将小村落从 11nn 编号,山贼集团的总部设在编号为 11 的小村落中。

山贼集团除了老大坐镇总部以外,其他的 pp 个部门希望在村落的其他地方(洛谷注:其实也包括总部)建立分部。pp 个分部可以在同一个小村落中建设,也可以分别建设在不同的小村落中,在不同的村落建设不同的分部需要花费不同的费用。

每个分部到总部的路径称为这个部门的管辖范围,于是这 pp 个分部的管辖范围可能重叠,或者完全相同。当多个分部管辖同一个村落时,他们之间可能发生矛盾,从而损失一部分利益,也可能相互合作,从而获取一部分利益。

请注意,如果相同的分部同时管辖多个村落,那么对于每个村落,都会计算一次收益损失/获取。

现在请你编写一个程序,确定 pp 个分部的位置,使得山贼集团能够获得最大的收益。

输入格式

输入的第一行有两个整数,分别代表村落数 nn 和山贼集团部门数量 pp

22 到第 nn 行,每行有两个整数 x,yx, y,代表存在一条连接村落 xx 和村落 yy 的道路。

(n+1)(n + 1) 到第 2n2n 行,每行 pp 个整数,第 (i+n)(i + n) 行的第 jj 个整数代表在第 ii 个村落建设第 jj 个部门的花费 ai,ja_{i, j}

(2n+1)(2n + 1) 行有一个整数,代表集团间相互影响利益的信息条数 tt

(2n+2)(2n + 2) 行到第 (2n+t+1)(2n + t + 1) 行,每行首先有一个整数 vv,若 vv 为正,则表示会获得额外的收益,vv 为负则表示会有损失。然后有一个整数 cc,代表涉及分部的数量。接下来有 cc 个整数,分别代表涉及的分部 xix_i。本条信息的含义为若这 cc 个分部同时管辖某个小村落(可能同时存在其他分部管辖该村落),则会产生额外收益或损失,其数值大小为 v|v|

输出格式

输出一行一个整数代表最大的收益。

2 1
1 2
2 
1
1
3 1 1
5

提示

样例输入输出 1 解释

22 号节点建立 11 号分部,花费为 11,则分部集合 {1}\{1\} 可以管辖 1,21, 2 两个节点,根据第一条信息,该集合每管辖一个节点会产生 33 的收益,因此总共产生了 2×3=62 \times 3 = 6 的收益,减去建立分部的花费,最大的收益为 61=56 - 1 = 5。可以证明不存在更优的方案。

数据规模与约定

对于 40%40\% 的数据,保证 1p61 \leq p \leq 6

对于 100%100\% 的数据,保证:

  • 1p121 \leq p \leq 121n1001 \leq n \leq 100
  • 1s,tn1 \leq s,t \leq n1ai,j1081 \leq a_{i, j} \leq 10^8
  • 1t2p1 \leq t \leq 2^p1v1081 \leq |v| \leq 10^81cp1 \leq c \leq p1xip1 \leq x_i \leq pxix_i 互不相同。
  • 答案的绝对值不超过 10810^8