以前写过，现在的码风与以前有些变化，主要是用数组模拟邻接表存图，以前是用指针存图。
以前的博文:http://www.cnblogs.com/Currier/p/6387732.html
洛谷可评测。
传送门：https://www.luogu.org/problem/show?pid=3381
1 program rrr(input,output); 2 const 3 inf=123456789; 4 type 5 etype=record 6 t,c,w,next,rev:longint; 7 end; 8 var 9 e:array[0..100010]of etype; 10 a,fre,frv,q,dis:array[0..5050]of longint; 11 inq:array[0..5050]of boolean; 12 n,m,s,t,i,j,x,y,c,w,max,ans,cnt,f:longint; 13 procedure add(x,y,c,w:longint); 14 begin 15 inc(cnt);e[cnt].t:=y;e[cnt].c:=c;e[cnt].w:=w;e[cnt].next:=a[x];a[x]:=cnt; 16 end; 17 function min(a,b:longint):longint; 18 begin 19 if a<b then exit(a) else exit(b); 20 end; 21 procedure spfa; 22 var 23 h,t:longint; 24 begin 25 for i:=1 to n do dis[i]:=inf; 26 fillchar(inq,sizeof(inq),false); 27 h:=0;t:=1;q[1]:=s;dis[s]:=0;inq[s]:=true; 28 while h<>t do 29 begin 30 inc(h);if h>5000 then h:=1; 31 i:=a[q[h]]; 32 while i<>0 do 33 begin 34 if (e[i].c>0) and (dis[q[h]]+e[i].w<dis[e[i].t]) then 35 begin 36 dis[e[i].t]:=dis[q[h]]+e[i].w; 37 frv[e[i].t]:=q[h];fre[e[i].t]:=i; 38 if not inq[e[i].t] then 39 begin 40 inc(t);if t>5000 then t:=1; 41 q[t]:=e[i].t;inq[e[i].t]:=true; 42 end; 43 end; 44 i:=e[i].next; 45 end; 46 inq[q[h]]:=false; 47 end; 48 end; 49 begin 50 assign(input,'r.in');assign(output,'r.out');reset(input);rewrite(output); 51 readln(n,m,s,t); 52 fillchar(a,sizeof(a),0);cnt:=0; 53 for i:=1 to m do 54 begin 55 readln(x,y,c,w); 56 add(x,y,c,w);e[cnt].rev:=cnt+1; 57 add(y,x,0,-w);e[cnt].rev:=cnt-1; 58 end; 59 max:=0;ans:=0; 60 while true do 61 begin 62 spfa; 63 if dis[t]=inf then break; 64 j:=t;f:=inf; 65 while j<>s do begin f:=min(f,e[fre[j]].c);j:=frv[j]; end; 66 max:=max+f; 67 j:=t;w:=0; 68 while j<>s do begin w:=w+e[fre[j]].w;dec(e[fre[j]].c,f);inc(e[e[fre[j]].rev].c,f);j:=frv[j]; end; 69 ans:=ans+w*f; 70 end; 71 write(max,' ',ans); 72 close(input);close(output); 73 end.