← 返回题目列表

AtCoder · awc0051_c

C. 项目选择

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

分数: 366 分

问题陈述

高桥作为公司新业务的负责人,正在尝试选择要执行的项目 N 项目建议书。每个项目要么执行,要么不执行,同一个项目不能执行多次。也可以不选择任何项目。

执行每个项目 i (1 \leq i \leq N) 需要花费 C_i 一万日元,利润为 P_i 一万日元。这里,利润和成本是独立的值,目标是最大化总利润。成本仅与预算约束相关,不会从利润中扣除。

但是,某些项目对由于团队任务竞争或共享设备而相互冲突,并且无法同时选择。有 M 这种冲突关系,以及 j-th (1 \leq j \leq M) 冲突关系表明两个项目 U_j 和项目 无法同时选择 V_j 。

高桥的预算限额是 K 一万日元。求所选项目的最大总利润,使得所选项目的总成本最多为 K 一万日元且无冲突关系,两个项目同时选定。

换句话说,让 S 是所选项目的集合,找到最大值 \displaystyle\sum_{i \in S} P_i 须满足以下所有条件:

  • \displaystyle\sum_{i \in S} C_i \leq K
  • 对于所有人 j (1 \leq j \leq M), U_j 和 V_j 不都包含在 S (即 \{U_j, V_j\} \not\subseteq S)

如果未选择任何项目(即 S 为空集),总利润为 0.

约束

  • 1 \leq N \leq 18
  • 0 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq K \leq 10^5
  • 1 \leq C_i \leq 10^5 (1 \leq i \leq N)
  • 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq U_j < V_j \leq N (1 \leq j \leq M)
  • 同一冲突关系不会被多次给出
  • 所有输入均为整数

输入

N M K
C_1 P_1
C_2 P_2
\vdots
C_N P_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • 第一行包含三个空格分隔的整数: N 代表项目数量, M 代表冲突关系的数量,以及 K 代表预算限制。
  • 从第 2 行到 (N + 1)第行,给出了每个项目的信息。
  • 的 (1 + i)第行 (1 \leq i \leq N) 包含成本 执行项目需要 C_i 执行项目所需的 i 和利润 获得 P_i ,以空格分隔。
  • 从 (N + 2)第 行 (N + M + 1)第行,给出了有关冲突关系的信息。如果 M = 0,这部分不存在。
  • 的 (N + 1 + j)第行 (1 \leq j \leq M) 包含项目编号 U_j 和 V_j 参与 j第一个冲突关系,用空格分隔。

输出

在单行上以整数形式输出所选项目的最大总利润。


示例输入 1

3 1 100
50 80
60 90
40 50
1 2

示例输出 1

140

示例输入 2

5 3 200
30 100
50 150
40 120
60 200
80 180
1 2
2 3
4 5

示例输出 2

420

示例输入 3

8 6 500
100 500
80 400
120 600
90 450
70 350
110 550
60 300
150 800
1 2
1 3
2 4
3 4
5 6
7 8

示例输出 3

2350