A6205. General Weighted Max Matching
编程题
普及+/提高
知识点
题目描述
有一个无向图，$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}$
> $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
75
说明/提示
- $2 \le N \le 16$
- $1 \le D_{i,j} \le 10^9$
**样例一解释**
选择 $D_{1,3},D_{2,4}$，总和为$5+8=13$。
- $1 \le D_{i,j} \le 10^9$
**样例一解释**
选择 $D_{1,3},D_{2,4}$，总和为$5+8=13$。