SAP模板【最大流】
感谢ZZX友情提供~
const maxe=1000000; maxn=40005; type edge=record x,y,next,op:longint; end; var e:array[0..maxe]of edge; a,gap,dis,pre,cur:array[0..maxn]of longint; n,m,i,j,k,s,t,u,v,cap,flow,mf:longint; procedure adde(u,v,cap,cc:longint); begin inc(k); e[k].y:=cap; e[k].x:=v; e[k].next:=a[u]; e[k].op:=k+1; a[u]:=k; inc(k); e[k].y:=cc; e[k].x:=u; e[k].op:=k-1; e[k].next:=a[v]; a[v]:=k; end; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; procedure sap; var i,j,k,now,p,pp,dist:longint; f:boolean; begin fillchar(dis,sizeof(dis),0); fillchar(gap,sizeof(gap),0); for i:=s to t do cur[i]:=a[i]; mf:=0; now:=s; gap[t]:=t; flow:=2147483647; while dis[s]<=t do begin if now=t then begin flow:=2147483647; i:=s; while i<>t do begin flow:=min(flow,e[cur[i]].y); i:=e[cur[i]].x; end; i:=s; while i<>t do begin dec(e[cur[i]].y,flow); inc(e[e[cur[i]].op].y,flow); i:=e[cur[i]].x; end; mf:=mf+flow; now:=s; end; p:=cur[now]; f:=true; while p<>0 do begin pp:=e[p].x; if (e[p].y>0) and (dis[now]=dis[pp]+1) then begin cur[now]:=p; pre[pp]:=now; now:=pp; f:=false; break; end; p:=e[p].next; end; if f then begin dec(gap[dis[now]]); if gap[dis[now]]=0 then break; cur[now]:=a[now]; p:=a[now]; dis[now]:=t+1; while p<>0 do begin pp:=e[p].x; if (e[p].y>0) then dis[now]:=min(dis[pp]+1,dis[now]); p:=e[p].next; end; inc(gap[dis[now]]); if now<>s then now:=pre[now]; end; end; end; begin //assign(input,'1.in'); //assign(output,'2.out'); //reset(input); //rewrite(output); read(n,m); s:=0; t:=n+1; for i:=1 to n do begin read(u,v); adde(s,i,u,0); adde(i,t,v,0); end; for i:=1 to m do begin read(u,v,cap); adde(u,v,cap,cap); end; sap; writeln(mf); //close(input); //close(output); end.</b>
发表回复