题目名称	12. 运输问题2
输入输出	`maxflowb.in/out`
难度等级	★★☆
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	cqw 于2008-03-19加入
开放分组	全部用户
提交状态
分类标签	图论网络流
	分享题解

通过：208，提交：392，通过率：53.06%
AAAAAAAAAA	100	0.000 s	0.00 MiB	C++
jhs	100	0.000 s	0.00 MiB	C++
BaDBoY	100	0.000 s	0.00 MiB	C++
Hzoi_QTY	100	0.000 s	0.00 MiB	C++
Pine	100	0.000 s	0.00 MiB	C++
神威难藏于泪	100	0.000 s	0.00 MiB	C++
猴	100	0.000 s	0.00 MiB	C++
APWTMECRD	100	0.003 s	0.46 MiB	C++
烟雨	100	0.003 s	0.46 MiB	C++
（ˇˍˇ）～耶稣	100	0.003 s	0.47 MiB	C++

关于运输问题2 的近10条评论(全部评论)
数据太弱。。。我写了个错解 90 分。。。（样例都没过） fsdh 2020-08-17 19:31 11楼
回复 @kito : 666 lyqlyqcogs 2017-08-10 08:22 10楼
回复 @하루Kiev : 膜大佬 BaDBoY 2017-07-31 09:07 9楼
莫名数组越界被水湮没不知所措 하루Kiev 2017-07-30 19:03 8楼
我带着调试信息输出居然A了九个点，原来前九个点的数据根本没有下界，忽略下界直接求最大流就能过9个点，唯一没过的第十个点居然是样例。神TM数据。 kito 2017-07-05 21:24 7楼
瞎写居然1a…… confoo 2017-03-09 15:23 6楼
不懂原理…… TenderRun 2016-07-21 21:43 5楼
有上下界的网络流首题留念。 /k 2016-03-16 20:02 4楼
回复 @TemplarAssassin : 恩呢。 stone 2016-03-16 19:01 3楼
推进能过，加上堆和标号就出错，…写渣了吗水中音 2014-12-24 06:33 2楼

12. 运输问题2

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

【问题描述】

一个工厂每天生产若干商品，需运输到销售部门进行销售。从产地到销地要经过某些城镇，有不同的路线可以行走，每条两城镇间的公路都有一定的流量限制。为了保证公路的运营效率，每条公路都有一个容量下界，也就是至少应有多少车辆通过。每条公路还有一个容量上界，也就是最多应有多少车辆通过。请你计算，在不考虑其它车辆使用公路的前提下，如何充分利用所有的公路，使产地运输到销地的商品最多，最多能运输多少商品。

【输入格式】

输入文件有若干行。

第一行，一个整数$n$，表示共有n个城市$(2<=n<=100)$，产地是$1$号城市，销地是$n$号城市。

下面有$n$行,每行有$2n$个数字。第$p$行第$2q-1$,$2q$列的数字表示城镇$p$与城镇$q$之间有无公路连接。数字为0表示无，大于0表示有公路，且这两个数字分别表示该公路流量的下界，上界。

【输出格式】

输出文件有一行。

第一行，1个整数$ans$，表示最大流量为$ans$。

【输入样例】

6
0 0 1 3 0 10 0 0 0 0 0 0
0 0 0 0 0 0 5 7 0 0 0 0
0 0 0 0 0 0 0 0 2 8 0 0
0 0 0 0 1 3 0 0 0 0 3 5
0 0 2 4 0 0 0 0 0 0 2 6
0 0 0 0 0 0 0 0 0 0 0 0

12. 运输问题2

【问题描述】

【输入格式】

【输出格式】

【输入样例】

【输出样例】