← 返回题目列表

AtCoder · awc0102_d

D. 研究课题的选择

中文机器翻译题面 查看原题

分数: 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