题目名称	750. 栅格网络流
输入输出	`flowa.in/out`
难度等级	★★☆
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	cqw 于2012-04-06加入
开放分组	全部用户
提交状态
分类标签
	分享题解

通过：44，提交：166，通过率：26.51%
_Itachi	100	0.005 s	0.83 MiB	C++
J_william	100	0.022 s	1.19 MiB	C++
AntiLeaf	100	0.028 s	69.18 MiB	C++
LCWhiStLe	100	0.034 s	1.57 MiB	C++
frontier	100	0.034 s	1.58 MiB	C++
可以的.	100	0.035 s	15.54 MiB	C++
digital-T	100	0.039 s	0.51 MiB	C++
隨風巽	100	0.040 s	0.41 MiB	C++
可以的.	100	0.040 s	25.83 MiB	C++
隨風巽	100	0.041 s	0.51 MiB	C++

本题关联比赛
20140423

关于栅格网络流的近10条评论(全部评论)
直接Dinic就过了...... AntiLeaf 2017-01-04 09:00 12楼
QAQ边数较少SPFA比较快 _Horizon 2015-07-27 15:20 11楼
回复 @隨風巽 : 好像确实不用longlong,我逗比了,我好像是因为INF定义小了的原因 Chenyao2333 2014-04-24 17:55 10楼
回复 @cstdio : 咦,好像就是呀,那正常的平面图对偶图求最短路怎么也可以过?>_<我被对偶图的性质和边的方向弄晕了........ Chenyao2333 2014-04-24 17:25 9楼
回复 @Chenyao2333 : 看样例的流…… cstdio 2014-04-23 19:07 8楼
回复 @Chenyao2333 : 不是。是无向边，可以看第4个数据。虽然根据水管可以推出是无向边，但是也不应该用箭头隨風巽 2014-04-23 15:16 7楼
回复 @隨風巽 : 不是有向边么? Chenyao2333 2014-04-23 15:13 6楼
这题应该不用long long 。但他搞个“—>"，意思竟然不是有向边。隨風巽 2014-04-23 15:12 5楼
这题告诉我们要随手写longlong 没事多写unsigned long long !!!!!!!!!!!!!!!!!!!!! Chenyao2333 2014-04-23 14:36 4楼
堆优化看起来没有用（不优化0.232s 优化后0.237s） >#< 这是怎么回事？？ SpaceQ 2013-05-26 18:59 3楼

750. 栅格网络流

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

【问题描述】

Bob 觉得一般图的最大流问题太难了，他不知道如何解决，于是他想尝试一个简单点的：栅格网络中的最大流问题，这个虽说简单了一点，但对 Bob 来说依旧太难，现在他有个麻烦需要你帮忙：给你一个 N*M 的栅格（如下所示），栅格中的边表示可以流水的管道，边上的数字表示管道的容量，举例说明：在下面图（ 2.6.1 ）中， (0,0) 和 (1,0) 之间边的容量为 6 ，这意味着这条边（水管）的最大水流量不超过 6 个单位。

N=3 M=3
图 2.6.1 栅格网络流

那么栅格中从 S 到 T 的最大流是多少呢 ? 换句话说 , 某一时刻最多能有多少单位的水从 S 流向 T?

【输入格式】

输入文件的第一行是一个正整数 T ，表示接下来有多少组测试数据。

每一组测试数据的第一行有两个正整数 N,M(1<=N,M<=100)

接着有两个矩阵H(N*(M-1)),V((N-1)*M)，H[i][j]表示(i,j)->(i,j+1)的流量；

V[i][j]表示(i,j)->(i+1,j)的流量。

【输出格式】

每一组测试数据输出只有一行，包含一个整数，即从 S(0,0) 到 T(N-1,M-1) 的栅格网络的最大流，不允许出现多余的空格。

【输入样例】

输入文件名： flowa .in

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

输出文件名： flowa .out

提示：下图 (2.6.2) 所示即为样例中栅格中的一个最大流。

N=3 M=3
图 2.6.2 一个解决方案