题目名称 738. [网络流24题] 数字梯形
输入输出 digit.in/out
难度等级 ★★★☆
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试数据 10
题目来源 GravatarMakazeu 于2012-04-05加入
开放分组 全部用户
提交状态
分类标签
网络流
分享题解
通过:136, 提交:258, 通过率:52.71%
GravatarAAAAAAAAAA 100 0.000 s 0.00 MiB C++
GravatarYoungsc 100 0.000 s 0.00 MiB C++
GravatarSamle 100 0.000 s 0.00 MiB C++
Gravatar小金 100 0.000 s 0.00 MiB C++
Gravatar‎MistyEye 100 0.004 s 0.33 MiB C++
GravatarZXCVBNM_1 100 0.004 s 0.36 MiB C++
Gravatar23333 100 0.004 s 0.36 MiB C++
GravatarceerRep 100 0.004 s 0.42 MiB C++
Gravatar 100 0.004 s 0.48 MiB C++
Gravatar23333 100 0.004 s 0.49 MiB C++
关于 数字梯形 的近10条评论(全部评论)
总是挂在如何给点编号上(无奈.jpg
Gravatarnew player
2018-04-01 21:53 10楼
我感觉这道题思维难度比餐巾低好多啊...
就是写的丑
GravatarCSU_Turkey
2018-01-02 16:05 9楼
非常好的题
GravatarAAAAAAAAAA
2017-08-04 17:58 8楼
这题好难,应该3星
Gravatarsplay
2017-03-12 10:26 7楼
苟利国家生死以,岂因祸福避趋之。
Gravatarinfinityedge
2017-02-05 13:17 6楼
好像从来没把边表开的合适过
Gravatar哒哒哒哒哒!
2017-01-11 08:59 5楼
居然才给两星。。好多比他简单的都两星半三星的。。
Gravatar_Itachi
2016-09-13 15:38 4楼
Gravatarvampire
2015-04-09 21:43 3楼
好久没写纯正的spfa了感觉好怀念…
Gravatar水中音
2015-03-19 07:51 2楼
http://conic.lofter.com/post/4387fa_438c6d1
GravatarSasuke
2014-12-13 08:45 1楼

738. [网络流24题] 数字梯形

★★★☆   输入文件:digit.in   输出文件:digit.out   简单对比
时间限制:1 s   内存限制:128 MiB

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

«编程任务:
对于给定的数字梯形,分别按照规则1,规则2,和规则3 计算出从梯形的顶至底的m
条路径,使这m条路径经过的数字总和最大。
«数据输入:
由文件digit.in提供输入数据。文件的第1 行中有2个正整数m和n(m,n<=20),分别
表示数字梯形的第一行有m个数字,共有n 行。接下来的n 行是数字梯形中各行的数字。
第1 行有m个数字,第2 行有m+1 个数字,…。
«结果输出:
程序运行结束时,将按照规则1,规则2,和规则3 计算出的最大数字总和输出到文件
digit.out中。每行一个最大总和。
输入文件示例 输出文件示例
digit.in
2 5
2 3
3 4 5
9 10 9 1
1 1 10 1 1

1 1 10 12 1 1

digit.out

66
75
77