我要招人

去企业版

首页 > 试题广场 >

图示是一个网络流从s到t的某时刻快照。此时t处一共接收到10

[单选题]

图示是一个网络流从s到t的某时刻快照。此时t处一共接收到10+13+16=39单位流量。每条横线上的数字表示当前流量和管道的容量。那么，该网络最大的流量是多少？

```
40
```
```
41
```
```
42
```
```
43
```

查看答案及解析

推荐

牛客813945号

s出流量最大为11+22+10=43，而由于t4只能接收10，s1必定损失1，而t5最大接收为16,2到5最大为17，t5满则5到6只能为1，这样t6最大为15，故流量最大为10+16+15=41，此时s3、23、25、t4、t5为满

故最大流量为41

此时满负荷为s3、23、25、t4、t5

编辑于 2015-01-28 11:07:20 回复(3)

Erya_尔雅

是这个图！

发表于 2017-11-07 17:40:22 回复(0)

Miss.Zhou

只是我一个人看不见图吗。。

发表于 2016-03-29 13:53:07 回复(12)

渣小白

其中的一种求解最大流量后的图，最大流量：10+16+15=41。

发表于 2017-08-01 23:04:42 回复(0)

Wills

s2,s3,23,36,25,4t,6t

发表于 2014-12-08 00:13:39 回复(0)

island

41。s1，s2，25,4t，s3，6t。

发表于 2014-11-08 14:56:02 回复(0)

啥

答案为41.

技巧：按层计算，瞻前顾后

首先计算每一层向终点方向的最大输出能力，不包括回流的量

然后计算总体的最大流量，为各个层中流量最小的一层的流量

本题中分为三层：

第一层为s。朝终点最大输出量为11+22+10 = 43

第二层为节点1、2、3。朝终点最大输出量为10+17+14 = 41（10是因为节点4最多接受10，出度为10，14是因为节点3的入度为14，所以是14而不是16）

第三层为节点4、5、6。朝终点最大输出量为10+16+16 = 42

所以综合考虑总体最大的流量只能41.

发表于 2015-07-27 16:47:42 回复(10)

Lyon

解析：最基本的求最大流。可以手动计算，答案为41。可以用最大流模板验证正确性：设s为1，t为8，那么中间结点的实际编号为上图编号+1. 数据如下：

【cpp】view plaincopyprint？

8 15

1 2  11

1 3  22

1 4  10

3 2  6

3 4  4

2 5  18

6 2  7

3 6  17

7 3  6

4 7  16

6 5  15

6 7  5

5 8  10

6 8  16

7 8  16

 

	一种方案为：

发表于 2014-10-25 00:25:55 回复(0)

牛客1512337号

图片说明

发表于 2018-05-23 20:55:16 回复(1)

牛客000001号

最大流量： 41

该题图中 s-1-2-6-5-t 是一条增广链 2-6是瓶颈，可以增加2个流量总流量= 39 + 2 = 41

没有出现新的满负荷的边，故图上的满负荷边就是最终最大流的满负荷边

满负荷边：6条

s-2 s-3 2-3 2-5 4-t 6-t

发表于 2015-08-22 19:07:29 回复(0)

simon_free

从左往右，按层计算，当前层各个出度与入度的权衡，入度小于出度，最大取入度；反之，则取出度值为最大值；然后综合考虑比较各个层级的值，取最小的值为最大值，木桶效应

发表于 2023-11-17 00:30:20 回复(0)

拖拉机代驾哒

根据@啥的回答我再整理一下自己的看法

第一层：最大输出量位11+22+10=43

第二层：中2号分给3号4个单位，分给1号1个单位，则总输出为12+17+14=43

第三层：此时4号只能输出10个单位，5号只能输出16，所以5号分一个单位到6号，6号就有15个单位，总输出为10+16+15=41

发表于 2020-03-04 16:27:17 回复(0)

牛客1637647号

他最大接收是41但是A最大发出只有40

发表于 2018-07-30 23:06:10 回复(0)

zfun

没想的那么复杂，从最后一层逐层倒推，在满足自身最大输出的前提下才给其他路回流，判断最大流量即可

发表于 2018-06-05 00:46:22 回复(0)

演戏不如看戏

为啥我看不到图

发表于 2017-11-20 09:57:52 回复(0)

郑志强

图没显示出来

发表于 2017-11-06 17:01:36 回复(0)

Forrestcloud

技巧：按层计算，瞻前顾后

首先计算每一层向终点方向的最大输出能力，不包括回流的量

然后计算总体的最大流量，为各个层中流量最小的一层的流量

发表于 2017-09-08 09:42:58 回复(0)

jokervsbat

图显示不出来......

发表于 2017-08-13 17:07:42 回复(0)

greatsir

手机上为什么看不到图

发表于 2016-09-15 10:37:10 回复(0)

瓜牛77

把残余网络画出来，再找一条通路，然后再计算残余网络，直到找不到通路为止。

发表于 2016-07-25 19:56:05 回复(0)

bruscar

正确答案是多少？是不是41？？？

发表于 2015-10-10 15:19:50 回复(0)

提交观点

问题信息

阿里巴巴图

上传者：小海豹

难度：

67条回答 1110收藏 26403浏览

图示是一个网络流从s到t的某时刻快照。此时t处一共接收到10

问题信息

热门推荐

相关试题