AT_arc056_c.[ARC056C] 部門分け

省选/NOI-

通过率：0%

AC君温馨提醒

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

题目描述

高桥君所在的公司有 $N$ 名员工。员工 $i$ 和员工 $j$ 之间有一个信任度 $w_{i,j}$ 。由于公司业务蒸蒸日上，现在需要将 $N$ 名员工分成若干个部门。这里，部门划分的得分定义为（部门数） $\times K$ 减去（属于不同部门的两人之间的信任度总和）。请编写程序，求得分的最大值。

输入格式

输入通过标准输入按以下格式给出。

$N$ $K$ $w_{1,1}$ ... $w_{1,N}$ : $w_{N,1}$ ... $w_{N,N}$

输出格式

输出第 $1$ 行，给出最大得分。

输入输出样例

输入#1
```
3 3
0 1 5
1 0 1
5 1 0
```
输出#1
```
4
```
输入#2
```
4 8
0 2 3 5
2 0 1 2
3 1 0 8
5 2 8 0
```
输出#2
```
11
```

输入#3

输出#3

说明/提示

限制条件

$1 \leq N \leq 17$
当 $i \neq j$ 时， $1 \leq w_{i,j} \leq 10^6$
$w_{i,i} = 0$
$w_{i,j} = w_{j,i}$
$1 \leq K \leq 10^6$
所有输入均为整数

部分得分

若能正确解决所有 $N \leq 9$ 的测试用例，可获得 $40$ 分。
若能正确解决所有 $N \leq 15$ 的测试用例，可额外获得 $40$ 分。

样例解释 1

如果将员工 $1$ 和 $3$ 分为一个部门，员工 $2$ 单独为一个部门，则部门数为 $2$ ，不同部门之间的信任度总和为 $2$ ，因此得分为 $2 \times 3 - 2 = 4$ 。没有比得分 $4$ 更高的划分方法。

由 ChatGPT 4.1 翻译

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

首页