← 返回题目列表

AtCoder · awc0017_d

D. 团队建设

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

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