分数: 400 分
问题陈述
高桥属于一个大学研究实验室,正在尝试选择本学期的研究课题。实验室有 N 候选研究主题,每个编号从 1 to N。致力于研究课题 i 需要花费 C_i 用于准备实验设备和材料,并且由此获得的学术成果的价值估计为 P_i.
有 M 研究主题之间的先决关系。的 j-th 先决关系由对表示 (U_j, V_j),这意味着如果您从事研究主题 U_j,您还必须从事研究课题 V_j (反过来不一定成立)。请注意,先决条件关系可能包含循环。例如,研究主题的情况 A 要求 B 作为先决条件和 B 要求 A 作为先决条件是可能的。在这种情况下,您不能仅选择其中之一 A 和 B;您必须选择两者或都不选择。
高桥选择一套 S (S \subseteq \{1, 2, \ldots, N\})要开展的研究课题。 S 必须满足所有先决关系。也就是说,对于所有 j = 1, 2, \ldots, M,如果研究主题 U_j 包含在 S,然后是研究主题 V_j 还必须包含在 S. S 可能是空集。
高桥的目标是最大化所选研究课题所获得成果的总价值减去总成本,即
\sum_{i \in S} (P_i - C_i)
If S 是空集,这个值为 0.
找到这个最大值。
约束
- 1 \leq N \leq 15
- 0 \leq M \leq \frac{N(N-1)}{2}
- 1 \leq P_i \leq 1000 (1 \leq i \leq N)
- 1 \leq C_i \leq 1000 (1 \leq i \leq N)
- 1 \leq U_j, V_j \leq N (1 \leq j \leq M)
- U_j \neq V_j (1 \leq j \leq M)
- 不存在重复的先决条件关系。也就是说,所有对 (U_j, V_j) 是不同的。然而,有可能 (U_j, V_j) = (V_k, U_k) 对于一些 j, k (即反向关系可以共存)。
- 先决关系可能包含循环。也就是说,由先决关系定义的有向图不一定是非循环的。
- 所有输入均为整数。
输入
N M P_1 C_1 P_2 C_2 \vdots P_N C_N U_1 V_1 U_2 V_2 \vdots U_M V_M
- 第一行包含研究主题的数量 N 和先决关系的数量 M,用空格分隔。
- 如下 N 行, i- 第行 (1 \leq i \leq N) 包含结果值 P_i 和成本 研究课题 C_i 研究课题的 i,用空格分隔。
- 如下 M 行, j- 第行 (1 \leq j \leq M) 包含 U_j 和 V_j 代表 j第一个前提关系,以空格分隔。这意味着如果您从事研究课题 U_j,您还必须从事研究课题 V_j.
输出
在单行中输出最大值 \sum_{i \in S} (P_i - C_i) 选择套装时 S 满足所有先决关系的研究主题。
示例输入 1
3 1 10 3 5 8 8 2 1 2
示例输出 1
10
示例输入 2
2 1 1 5 2 6 1 2
示例输出 2
0
示例输入 3
6 5 20 13 15 19 18 14 10 13 25 10 8 20 1 2 2 1 3 4 5 6 6 5
示例输出 3
7
示例输入 4
10 12 50 30 40 45 30 10 25 40 60 20 35 50 20 15 45 25 10 30 55 35 1 2 2 3 3 1 4 5 5 6 6 4 7 8 8 9 9 7 10 1 4 7 8 10
示例输出 4
70
示例输入 5
1 0 5 3
示例输出 5
2