var sink,source,n,m,i,x,y,sum,ans:longint;//sink=汇点,source=源点 table:array[1..3000,1..3000] of longint; last,flow:array[1..100000] of longint;//我们是找到一条增广路才进行增广和反向边,所以要last记录前继点,也就是 什么点到了i这个点=last[i]。flow用来记录到某个点的最大flow值
FunctionBfs:longint;//Bfs部分 var head,tail,i,k:longint; will:array[1..100000] of longint;//队列 begin for i:=1to n do last[i]:=-1; last[source]:=0;//这个应该懂
while head<=tail do begin k:=will[head]; inc(head); if k=sink then//到达汇点,立马结束! break;
for i:=1to n do if (table[k,i]>0)and(last[i]=-1) then//找到新点 begin last[i]:=k; flow[i]:=min(table[k,i],flow[k]);
inc(tail); will[tail]:=i; end; end;
if last[sink]=-1then//找不到?? exit(-1); Bfs:=flow[sink];//这一条路径的flow end;
ProcedureEdmonds_Karp; var increase,k:longint; begin increase:=Bfs; while increase<>-1do begin k:=sink; while k<>source do begin dec(table[last[k],k],increase);//减少正向边 inc(table[k,last[k]],increase);//增加反向边(建造) k:=last[k];//继续 end; inc(ans,increase);//增加答案 increase:=Bfs;//increase用来存储这条边的最大流量 end; end;
begin read(m,n,source,sink); //主程序才是一个程序最难理解的地方! for i:=1to n do begin read(x,y,sum); inc(table[x,y],sum); //必须inc!! end; Edmonds_Karp; writeln(ans);//才怪 end.
var next,reach,value,cnt:array[-1..200000] of longint; //这次我用到了链式前向星,不会的请认真学习 dep:array[0..200000] of longint;//分层,深度 will:array[1..200000] of longint;//队列 cur:array[1..200000] of longint;//当前弧优化 n,m,sink,source,i,x,y,sum,tot,maxflow:longint;
procedureadd(x,y:longint);//链式前向星 begin inc(tot); reach[tot]:=y; value[tot]:=sum; next[tot]:=cnt[x]; cnt[x]:=tot; end;
functionBfs:boolean;//分层 var head,tail,now,i:longint; begin fillchar(dep,sizeof(dep),0);//清空为0 dep[source]:=1; head:=1; tail:=1; will[1]:=source;
while head<=tail do//Bfs队列开始 begin now:=will[head]; inc(head); i:=cnt[now]; while i<>-1do begin if (value[i]>0)and(dep[reach[i]]=0) then//没有被赋值Dep begin dep[reach[i]]:=dep[now]+1;//You know inc(tail); will[tail]:=reach[i]; end; i:=next[i]; end; end;
if dep[sink]=0then exit(False);//不能分层,汇点没有被赋值 Bfs:=True; end;
functionDfs(now,now_flow:longint):longint;//now为现在点,now_flow为现在的流量(最优) var flow,i,flow_,now_flow_:longint; begin flow:=0; flow_:=0; now_flow_:=now_flow; if now=sink then exit(now_flow);
i:=cur[now]; while i<>-1do begin if (dep[reach[i]]=dep[now]+1)and(value[i]>0) then//我说过了,必须同一层! 而且要有连边才行value[i]>0 begin flow:=Dfs(reach[i],min(now_flow_,value[i]));//神奇的大法师? if flow>0then begin dec(value[i],flow); inc(value[i xor 1],flow); inc(flow_,flow);//对比EK优化之处 dec(now_flow_,flow);//对比EK优化之处 if now_flow_=0then//同上 break; end; end; i:=next[i]; end; exit(flow_);//加上本边后最优的流量 end;
procedureDinic; var tmp,i:longint; begin
while Bfs do//如果还能分层(增广) while1<2do//大佬式优化 begin for i:=1to n do cur[i]:=cnt[i];//当前弧优化 tmp:=dfs(source,maxlongint);//这一次整个图增广的流量 if tmp=0then break; inc(maxflow,tmp);//answer end; end;
procedureRead_; begin read(n,m,source,sink); filldword(cnt,sizeof(cnt) div4,maxlongint*2+1);//清空数组filldword(数组名字,sizeof(数组名字) div 4,maxlongint*2+1);=变为-1 filldword(next,sizeof(next) div4,maxlongint*2+1); for i:=1to m do begin read(x,y,sum);//链式前向星 add(x,y); dec(sum,sum); add(y,x); end; end;
begin tot:=1; //必须必须必须必须,以正式的惨案告诉你们:极限数据AC,普通数据WA read_;//输入 Dinic; writeln(maxflow);//answer end.