#最小割 #图 > [!quote] 题目背景 > > （接 [[挑选鱼鱼]]） > > 好渴鹅已经攻打完了好鱼鱼王国，带回来了一大批鱼鱼战俘。 ## 题目描述 鱼鱼们排成了一个 $n\times m$ 的矩阵，现在好渴鹅想要挑选一些鱼鱼，把他们一起炖出来吃掉。不过，鱼鱼们会像“马”字一样跳跃，而鱼鱼们彼此之间非常不和谐。因此如果你选出来的鱼鱼可以互相跳跃并吃掉对方的话，那么你的晚餐就没有着落了，并且还会被好渴鹅长官给暴打一顿。 现在每一个鱼鱼都有一定的美味值，你需要选择一个鱼鱼们之间都不会互相吃掉并且美味值和最大的方案，输出这个美味值和。 ## 输入格式 - 第一行：$n,m$； - 接下来：$n$ 行，第 $i$ 行第 $j$ 列上面的数字 $a_{i,j}$ 描述了位于 $(i,j)$ 位置的好鱼鱼美味值。 ## 输出格式 直接输出答案就行了。 ## 提示说明 ### 样例解释 先选择 $(3,1),(2, 2),(3, 2)$，然后在 $(3, 3)$ 和 $(2, 1)$ 之间任选一个。 ### 数据范围 - $1\le n,m\le 500$; - $1\le \max\limits_{i=1}^{n}\max\limits_{j=1}^{m}a_{i,j}\le 10^9$。