A90655.General Weighted Max Matching

普及+/提高

通过率：0%

时间限制：1.00s

内存限制：128MB

题目描述

有一个无向图， $i$ 到 $j$ 的距离为 $D_{i,j}$ 。你可以选择一些边，使得这些边连接的所有顶点互不相同。求这些边总长度的最大值。

输入格式

以以下格式输入：

$N$
$D_{1,2},D_{1,3},\ldots,D_{1,N}$
$D_{2,3},\ldots,D_{2,N}$
$\vdots$
$D_{N-1,N}$

输出格式

$1$ 个整数。如题意。

输入输出样例

输入#1
```
4
1 5 4
7 8
6
```
输出#1
```
13
```
输入#2
```
3
1 2
3
```
输出#2
```
3
```

输入#3

16
5 6 5 2 1 7 9 7 2 5 5 2 4 7 6
8 7 7 9 8 1 9 6 10 8 8 6 10 3
10 5 8 1 10 7 8 4 8 6 5 1 10
7 4 1 4 5 4 5 10 1 5 1 2
2 9 9 7 6 2 2 8 3 5 2
9 10 3 1 1 2 10 7 7 5
10 6 1 8 9 3 2 4 2
10 10 8 9 2 10 7 9
5 8 8 7 5 8 2
4 2 2 6 8 3
2 7 3 10 3
5 7 10 3
8 5 7
9 1
4

输出#3

说明/提示

$2 \le N \le 16$
$1 \le D_{i,j} \le 10^9$

样例一解释

选择 $D_{1,3},D_{2,4}$ ，总和为 $5+8=13$ 。

首页