分数: 366 分
问题陈述
高桥负责在他的公司组建一个项目团队。
有 N 公司员工,每人分配一个员工编号 1 to N。员工能力值 i is A_i.
高桥决定准确选择 K 员工 N 员工组成团队。同一员工不能被多次选择,并且每个员工要么被选入团队,要么不被选入团队。
但是,某些员工之间可能存在兼容性问题。 M 给出“不兼容对”,其中 j第对由员工组成 U_j 和员工 V_j。如果 两者 这些员工被选入团队,他们的协调性受到影响,团队的整体实力下降了 B_j。如果仅选择一对中的一个,或者两者都不选择,则不会发生减少。
具体来说,让 S (S \subseteq \{1, 2, \ldots, N\}, |S| = K) 是员工编号的集合 K 选定的员工。团队整体实力定义如下:
\sum_{i \in S} A_i \ - \sum_{\substack{1 \leq j \leq M \\ U_j \in S \text{ and } V_j \in S}} B_j
也就是说,它是总能力值 K 选定的员工减去所有不兼容对(其中两个成员都包含在其中)的总减少量 S.
当高桥选择 K 员工要最大化团队的整体实力,寻找团队整体实力的最大价值。请注意,整体强度可能为负,但即使在这种情况下,也按原样输出最大值。
约束
- 1 \leq N \leq 18
- 0 \leq M \leq \frac{N(N-1)}{2}
- 1 \leq K \leq N
- 1 \leq A_i \leq 10^9
- 1 \leq U_j < V_j \leq N
- 1 \leq B_j \leq 10^9
- 全部 (U_j, V_j) 是不同的
- 所有输入值均为整数
输入
N M K A_1 A_2 \ldots A_N U_1 V_1 B_1 U_2 V_2 B_2 \vdots U_M V_M B_M
- 第一行包含员工人数 N,不兼容对的数量 M,以及为团队选择的员工人数 K,用空格分隔。
- 第二行包含每个员工的能力值 A_1, A_2, \ldots, A_N,用空格分隔。
- 以下 M 行(从第 3 行到 (M + 2)第行)包含有关不兼容对的信息。如果 M = 0,这部分不存在。
- 的 (2 + j)-第行包含员工编号 U_j 和 V_j 形成 j- 第一个不相容的配对,以及整体实力的下降 B_j,用空格分隔。
输出
单行输出队伍整体实力的最大值。
示例输入 1
4 2 2 10 8 6 5 1 2 3 3 4 2
示例输出 1
16
示例输入 2
5 4 3 100 90 80 70 60 1 2 50 1 3 40 2 3 30 4 5 10
示例输出 2
220
示例输入 3
8 6 4 1000000000 900000000 800000000 700000000 600000000 500000000 400000000 300000000 1 2 500000000 1 3 400000000 2 3 300000000 1 4 200000000 5 6 100000000 7 8 50000000
示例输出 3
2700000000