CF1184B3 The Doctor Meets Vader (Hard)

叛军已经积攒了足够的黄金，准备发动全面进攻。现在局势逆转，叛军将派遣飞船攻击帝国基地！ 银河系可以表示为一个无向图，包含 $n$ 个行星（节点）和 $m$ 个虫洞（边），每条边连接两个行星。 共有 $s$ 艘叛军飞船和 $b$ 个帝国基地，分别位于银河系中的不同行星上。 每艘飞船有一个位置 $x$，表示其所在行星的编号，攻击力 $a$，一定量的燃料 $f$，以及操作费用 $p$。 每个基地有一个位置 $x$，防御力 $d$，以及一定数量的黄金 $g$。 如果同时满足以下两个条件，飞船可以攻击基地： - 飞船的攻击力大于等于基地的防御力； - 飞船的燃料大于等于飞船所在节点与基地所在节点之间的最短距离（以虫洞数计）。 叛军战士非常自豪。如果一艘飞船无法攻击任何基地，则没有叛军飞行员愿意操作它。 如果一艘飞船被操作，其产生的利润等于其攻击的基地的黄金数量减去操作该飞船的费用。注意，这个值可能为负数。被操作的飞船会选择攻击能使其利润最大的基地。 达斯·维达总是喜欢表现得很富有。因此，每当一个基地被攻击并且黄金被劫走时，他会立即为该基地补充黄金。 因此，对于叛军来说，多艘飞船可以攻击同一个基地，每艘飞船都能获得该基地的全部黄金。 叛军委托 Heidi 和 Doctor 决定应操作哪些飞船，以使总利润最大。 然而，战争持续已久，飞行员们之间建立了牢不可破的友谊，有些飞行员如果朋友不操作飞船，他们也拒绝操作。 他们有 $k$ 条依赖关系，每条为 $s_1, s_2$，表示只有在飞船 $s_2$ 也被操作时，飞船 $s_1$ 才能被操作。

第一行输入两个整数 $n$ 和 $m$（$1 \leq n \leq 100$，$0 \leq m \leq 10000$），分别表示节点数和边数。 接下来 $m$ 行，每行两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$），表示一条无向边连接节点 $u$ 和 $v$。 下一行输入三个整数 $s$、$b$ 和 $k$（$1 \leq s, b \leq 10^5$，$0 \leq k \leq 1000$），分别表示飞船数、基地数和依赖关系数。 接下来 $s$ 行，每行四个整数 $x, a, f, p$（$1 \leq x \leq n$，$0 \leq a, f, p \leq 10^9$），表示飞船的位置、攻击力、燃料和操作费用。飞船编号为 $1$ 到 $s$。 接下来 $b$ 行，每行三个整数 $x, d, g$（$1 \leq x \leq n$，$0 \leq d, g \leq 10^9$），表示基地的位置、防御力和黄金数量。 接下来 $k$ 行，每行两个整数 $s_1$ 和 $s_2$（$1 \leq s_1, s_2 \leq s$），表示飞船 $s_1$ 对飞船 $s_2$ 的依赖关系。

输出一个整数，表示可以获得的最大总利润。

最优策略是操作第 1、2、4 号飞船，分别攻击第 1、1、2 号基地。 由 ChatGPT 4.1 翻译