分数: 400 点
问题陈述
给你一个带权无向完全图 N 顶点编号自 1 to N。连接顶点的边 i 和 j (i< j) 的权重为 D_{i,j}.
在以下条件下选择一定数量的边时,求所选边的最大可能总权重。
- 所选边的端点成对不同。
约束
- 2\leq N\leq 16
- 1\leq D_{i,j} \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
D_{1,2} D_{1,3} \ldots D_{1,N}
D_{2,3} \ldots D_{2,N}
\vdots
D_{N-1,N}
输出
将答案打印为整数。
示例输入 1
4 1 5 4 7 8 6
示例输出 1
13
如果选择连接顶点的边 1 和 3,以及连接顶点的边 2 和 4,边的总权重为 5+8=13.
可以证明这是可达到的最大值。
示例输入 2
3 1 2 3
示例输出 2
3
N 可以是奇数。
示例输入 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