General Weighted Max Matching

题目描述

你得到一个带权无向完全图，顶点编号为 $1$ 到 $N$。连接顶点 $i$ 和 $j$ (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}$

输出格式

以整数形式输出答案。

4
1 5 4
7 8
6

13

3
1 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

75

提示

$2\leq N\leq 16$ $1\leq D_{i,j} \leq 10^9$ 所有输入值均为整数。如果你选择连接顶点 $1$ 和 $3$ 的边，以及连接顶点 $2$ 和 $4$ 的边，边的权重总和为 $5+8=13$。 可以证明这是可达到的最大值。
$N$ 可能为奇数。

标签: AtCoder|abc318D

来源

AtCoder|abc318D