UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2310. ParkII

统计 下载数据

Description

Hnoi2007-Day1有一道题目 Park:给你一个 m * n 的矩阵,每个矩阵内有个
权值V(i,j) (可能为负数),要求找一条回路,使得每个点最多经过一次,并且经过
的点权值之和最大,想必大家印象深刻吧.
无聊的小 C 同学把这个问题稍微改了一下:要求找一条路径,使得每个点
最多经过一次,并且点权值之和最大,如果你跟小 C 一样无聊,就麻烦做一下
这个题目吧.

Input

第一行 m, n,接下来 m行每行 n 个数即. 
V( i,j)

Output

一个整数表示路径的最大权值之和.

Sample Input

2 3
1 -2 1
1 1 1

Sample Output

5
【数据范围】
30%的数据,n≤6.
100%的数据,m<=100,n ≤ ≤8.
注意:路径上有可能只有一个点.

Hint

Source