← 返回题目列表

AtCoder · abc318_d

G. 通用加权最大匹配

中文机器翻译题面 查看原题

分数: 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