Description
Every time it rains on Farmer John's fields, a pond forms over Bessie's favorite clover patch. This means that the clover is covered by water for awhile and takes quite a long time to regrow. Thus, Farmer John has built a set of drainage ditches so that Bessie's clover patch is never covered in water. Instead, the water is drained to a nearby stream. Being an ace engineer, Farmer John has also installed regulators at the beginning of each ditch, so he can control at what rate water flows into that ditch. Farmer John knows not only how many gallons of water each ditch can transport per minute but also the exact layout of the ditches, which feed out of the pond and into each other and stream in a potentially complex network. Given all this information, determine the maximum rate at which water can be transported out of the pond and into the stream. For any given ditch, water flows in only one direction, but there might be a way that water can flow in a circle.Input
The input includes several cases. For each case, the first line contains two space-separated integers, N (0 <= N <= 200) and M (2 <= M <= 200). N is the number of ditches that Farmer John has dug. M is the number of intersections points for those ditches. Intersection 1 is the pond. Intersection point M is the stream. Each of the following N lines contains three integers, Si, Ei, and Ci. Si and Ei (1 <= Si, Ei <= M) designate the intersections between which this ditch flows. Water will flow through this ditch from Si to Ei. Ci (0 <= Ci <= 10,000,000) is the maximum rate at which water will flow through the ditch.Output
For each case, output a single integer, the maximum rate at which water may emptied from the pond.Sample Input
5 4 1 2 40 1 4 20 2 4 20 2 3 30 3 4 10Sample Output
50Source
注：今天刚刚把最大流的基本问题搞明白，就练练这道题目，顺便简单介绍一下标号法求最大流的思想。 1.首先需要明白增广链的定义，这个可以查一下其他资料； 2.我们的目的是寻找每一条增广链，增大流量，直到所有的增广链都经过了扩大，即没有了增广链，这时得到的流肯定是最大流； 3.标号法是指对于每一个节点i，将与它相连的所有的未经过处理节点的p值赋为i以表示是有i找到的，如果是f[i,j]<c[i,j]即正向边不是饱和边，就将d:=min(d,c[i,j]-f[i,j])，如果是反向边并且属于非零流边，令d:=min(d,f[i,j])。 4.很明显3中的d是一个特殊的值，对于所有的正向边加上d反向边减去d不会影响这条路的可行流性质 5.一直执行2~3过程，直到不存在增广链。 上文讲的并不透彻，希望大家可以多看些课件，等我熟练后在写出更大众化的东西。 1 var 2 v:array[ 0 .. 300 ] of boolean; 3 p:array[ 0 .. 300 ] of longint; 4 f,c:array[ 0 .. 300 , 0 .. 300 ] of longint; 5 i,j,k,m,n,ans,w:longint; 6 7 procedure findmax; 8 var 9 i,j,d:longint; 10 begin 11 while true do 12 begin 13 fillchar(v, sizeof (v), 0 ); 14 fillchar(p, sizeof (p), 0 ); 15 d: = maxlongint; 16 repeat 17 i: = 0 ; 18 p[ 1 ]: = maxlongint; 19 repeat 20 inc(i); 21 until (i > n)or((not v[i])and(p[i] <> 0 )); 22 if i > n then break ; 23 for j: = 1 to n do if not v[j] then 24 if p[j] = 0 then 25 begin 26 if f[i,j] < c[i,j] then 27 begin 28 p[j]: = i; 29 if c[i,j] - f[i,j] < d then d: = c[i,j] - f[i,j]; 30 end else 31 if f[j,i] > 0 then 32 begin 33 p[j]: =- i; 34 if f[j,i] < d then d: = f[j,i]; 35 end; 36 end; 37 v[i]: = true ; 38 until p[n] <> 0 ; 39 if p[n] = 0 then break ; 40 i: = n; 41 repeat 42 j: = i; i: = abs(p[j]); 43 if p[j] < 0 then dec(f[j,i],d) 44 else inc(f[i,j],d); 45 until i = 1 ; 46 end; 47 end; 48 49 begin 50 while not eof do 51 begin 52 readln(m,n); 53 ans: = 0 ; 54 fillchar(f, sizeof (f), 0 ); 55 fillchar(c, sizeof (c),$ff); 56 for i: = 1 to m do 57 begin 58 readln(j,k,w); 59 if c[j,k] =- 1 then c[j,k]: = w else inc(c[j,k],w); 60 end; 61 findmax; 62 for i: = 1 to n do 63 for j: = 1 to n do 64 if (v[i])and(not v[j]) then 65 if c[i,j] > 0 then inc(ans,c[i,j]); 66 writeln(ans); 67 end; 68 end.这是刚刚实现的队列写的代码：
1 var 2 q:array[ 0 .. 30000 ] of longint; 3 f,c:array[ 0 .. 200 , 0 .. 200 ] of longint; 4 p:array[ 0 .. 200 ] of longint; 5 v:array[ 0 .. 200 ] of boolean; 6 i,j,k,m,n,ans,w:longint; 7 8 procedure findmax; 9 var 10 head,tail,now:longint; 11 i,j,d:longint; 12 begin 13 while true do 14 begin 15 fillchar(q, sizeof (q), 0 ); 16 fillchar(p, sizeof (p), 0 ); 17 fillchar(v, sizeof (v), 0 ); 18 head: = 1 ; tail: = 1 ; d: = maxlongint; 19 v[ 1 ]: = true ; p[ 1 ]: = maxlongint; q[ 1 ]: = 1 ; 20 while head <= tail do 21 begin 22 now: = q[head]; 23 for i: = 1 to n do 24 if not v[i] then 25 begin 26 if f[now,i] < c[now,i] then 27 begin 28 if d > c[now,i] - f[now,i] then 29 d: = c[now,i] - f[now,i]; 30 p[i]: = now; 31 v[i]: = true ; inc(tail); q[tail]: = i; 32 end else 33 if f[i,now] > 0 then 34 begin 35 if d > f[i,now] then d: = f[i,now]; 36 p[i]: =- now; 37 v[i]: = true ; inc(tail); q[tail]: = i; 38 end; 39 end; 40 inc(head); 41 end; 42 if not v[n] then break ; 43 i: = n; 44 while i <> 1 do 45 begin 46 j: = i; i: = abs(p[j]); 47 if p[j] < 0 then dec(f[j,i],d) 48 else inc(f[i,j],d); 49 end; 50 end; 51 for i: = 1 to tail do 52 for j: = 1 to n do 53 if not v[j] then 54 inc(ans,c[q[i],j]); 55 end; 56 57 begin 58 assign(input, ' ditch.in ' ); reset(input); 59 assign(output, ' ditch.out ' ); rewrite(output); 60 readln(m,n); 61 ans: = 0 ; 62 for i: = 1 to m do 63 begin 64 readln(j,k,w); 65 inc(c[j,k],w); 66 end; 67 findmax; 68 writeln(ans); 69 close(input); close(output); 70 end.转载于:https://www.cnblogs.com/reflec94/archive/2011/03/31/2001381.html
