【codevs1913】数字梯形问题

2014年2月21日1,6350

题目描述 Description

给定一个由n 行数字组成的数字梯形如下图所示。梯形的第一行有m 个数字。从梯形
的顶部的m 个数字开始,在每个数字处可以沿左下或右下方向移动,形成一条从梯形的顶
至底的路径。
规则1:从梯形的顶至底的m条路径互不相交。
规则2:从梯形的顶至底的m条路径仅在数字结点处相交。
规则3:从梯形的顶至底的m条路径允许在数字结点相交或边相交。

对于给定的数字梯形,分别按照规则1,规则2,和规则3 计算出从梯形的顶至底的m
条路径,使这m条路径经过的数字总和最大。

输入描述 Input Description

 

第1 行中有2个正整数m和n(m,n<=20),分别
表示数字梯形的第一行有m个数字,共有n 行。接下来的n 行是数字梯形中各行的数字。
第1 行有m个数字,第2 行有m+1 个数字,…。

输出描述 Output Description

将按照规则1,规则2,和规则3 计算出的最大数字总和输出

样例输入 Sample Input

每行一个最大总和。

样例输出 Sample Output

2 5
2 3
3 4 5
9 10 9 1
1 1 10 1 1
1 1 10 12 1 1

数据范围及提示 Data Size & Hint

66
75
77

题解

将蚯蚓的游戏略加改动

1、与蚯蚓的游戏规则一完全相同

2、规则二,由于可以共点,所以就不用拆点了,源点与上层继续保持容量为1,并一将底层与汇点的容量限制改为无穷大即可,其它类似,

3、规则三,由于边和节点都可以共用,此时没有必要把原网络销毁,直接在上一个规则的前提下修改每一条边的容量即可(注意源点与顶层节点之间的容量还是1,否则就无法满足是m条路径取得的最大值,其他边的容量改成无穷大即可)