AT_past18_m.グループ分け

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有 $N$ 个人，编号为 $1$ 到 $N$ 。第 $i$ 个人有 $A_i$ 颗糖果。

此外，给定 $M$ 组关系，每组 $(X_1, Y_1),\ldots,(X_M, Y_M)$ 表示这两个人关系不好。

请你将 $N$ 个人划分到若干个组内，使得满足以下两个条件时，所需组数最少：

每个组内所有人的糖果总数不超过 $S$ 。
任意关系不好的一对人，不能在同一个组内。

输入格式

输入从标准输入读入，格式如下：

$N$ $M$ $S$ $A_1$ $A_2$ $\ldots$ $A_N$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_M$ $Y_M$

输出格式

输出最小的满足条件的分组数。

输入输出样例

输入#1
```
3 1 10
2 3 4
1 2
```
输出#1
```
2
```
输入#2
```
5 0 10
2 3 4 10 10
```
输出#2
```
3
```

输入#3

19 10 13639949
6248137 1929297 1115672 3165903 771666 2658398 3460632 3239969 5759071 1396990 5625214 7940774 1755330 7704375 8252319 2891254 3580852 7211614 6847141
11 17
1 11
9 10
10 16
11 19
4 14
2 9
9 19
9 11
17 19

输出#3

说明/提示

样例解释 1

第 $1$ 个人与第 $2$ 个人关系不好，因此不能在同一组。我们可以将他们分成两个组，一个组只有第 $1$ 个人，另一个组有第 $2$ 和第 $3$ 个人，这样满足条件。

样例解释 2

可以分为三个组：一个组有 $1, 2, 3$ 号，另一个组只有 $4$ 号，最后一个组只有 $5$ 号，也可以满足要求。

数据范围

$1 \leq N \leq 20$
$0 \leq M \leq \frac{N(N-1)}{2}$
$1\leq X_i < Y_i \leq N$
$(X_i, Y_i)$ 均不相同
$0 \leq A_i \leq 10^7$
$\max_i A_i \leq S \leq 10^9$
所有输入均为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页