一般带权最大匹配

题目描述

给定一个顶点编号为 $1$ 到 $N$ 的带权无向完全图。连接顶点 $i$ 和顶点 $j$($i \lt j$)的边的权值为 $D_{i,j}$。

在满足以下条件的前提下选择若干条边,求所选边的权值总和的最大可能值。

所选边的端点两两不同。

输入格式

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

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

输出格式

以整数形式输出答案。

样例

4
1 5 4
7 8
6

13

如果选择连接顶点 $1$ 和顶点 $3$ 的边,以及连接顶点 $2$ 和顶点 $4$ 的边,则边的权值总和为 $5+8=13$。

可以证明这是可达的最大值。

3
1 2
3

3

$N$ 可以为奇数。

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 \le N \le 16$
• $1 \le D_{i,j} \le 10^9$
• 所有输入值均为整数。