Moving the Hay

时间限制：5s 空间限制：64MB

题目描述

After he partitioned his farm into R (1 <= r="" <="200)" rows="" and="" c="" (1="" squares="" conveniently="" labeled="" 1,1="" through="" r,c,="" farmer="" john="" spent="" days="" cutting="" the="" hay="" stacking="" a="" huge="" amount="" of="" it="" in="" square="" 1,1.="" he="" then="" undertook="" task="" mapping="" out="" n="" haypaths="" farm="" so="" that="" could="" deduce="" maximum="" rate="" move="" from="" to="" r,c.="" each="" haypath="" uniquely="" connects="" middle="" two="" rectilinearly="" adjacent="" partitioned="" has="" some="" capacity="" limit="" l_i="" is="" can="" be="" transported="" either="" direction="" across="" haypath.="" he's="" just="" positive="" at="" reasonable="" other="" side="" but="" doesn't="" know="" what="" fastest="" is.="" help="" him="" learn="" it.="" p="">

输入格式

* Line 1: Three separated integers: R, C, and N * Lines 2..N+1: Line i+1 describes path i with five space-separated integers: r1, c1, r2, c2, and L_i which denote a haypath connecting (r1,c1) to (r2,c2) with capacity L_i.

输出格式

* Line 1: One number, on a line by itself, the maximum amount of material which can be transported from (1,1) to (R,C) simultaneously.

样例输入

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

INPUT DETAILS:

The grid is as follows:
*--5--* . . *
|     |     
3     5     :
|     |    
*--2--*--1--*
      |     |
:     6     4
      |     |
* . . *--7--*

样例输出

提示

Consider the two edges coming out of (2,2), at most 6+1=7 units of hay can be transported. This is indeed feasible.

题目来源

没有写明来源