bzoj 1797: [Ahoi2009]Mincut 最小割 (网络流)

太神了直接看了hzwer的题解,有个新认识,一条路径上满流的一定是这条路径上所有边的最小值。

type
arr=record
toward,next,cap,from:longint;
end;
const
maxm=;
maxn=;
var
edge:array[..maxm]of arr;
first,cur,d,p,gap:array[..maxn]of longint;
chose1,chose2:array[..maxn]of boolean;
n,m,s,t,tot,esum:longint; function min(x,y:longint):longint;
begin
if x<y then exit(x);
exit(y);
end; procedure add(j,k,l:longint);
begin
inc(esum);
edge[esum].from:=j;
edge[esum].toward:=k;
edge[esum].next:=first[j];
first[j]:=esum;
edge[esum].cap:=l;
end; procedure addedge(j,k,l:longint);
begin
add(j,k,l);
add(k,j,);
end; function sap(x,flow:longint):longint;
var
now,more,i,too:longint;
begin
if x=t then exit(flow);
now:=;
i:=cur[x];
while i>= do begin
too:=edge[i].toward;
if (d[x]=d[too]+) and (edge[i].cap>) then begin
more:=sap(too,min(flow-now,edge[i].cap));
dec(edge[i].cap,more);
inc(edge[i xor ].cap,more);
inc(now,more);
cur[x]:=i;
if now=flow then exit(flow);
end;
i:=edge[i].next;
end;
dec(gap[d[x]]);
if gap[d[x]]= then d[s]:=n;
inc(d[x]);
inc(gap[d[x]]);
cur[x]:=first[x];
exit(now);
end; procedure maxflow;
var
i:longint;
begin
fillchar(d,sizeof(d),);
fillchar(gap,sizeof(gap),);
gap[]:=n;
for i:= to n do cur[i]:=first[i];
while d[s]<n do sap(s,maxlongint);
end; procedure into;
var
i,j,k,l:longint;
begin
esum:=-;
fillchar(first,sizeof(first),);
readln(n,m,s,t);
for i:= to m do begin
readln(j,k,l);
addedge(j,k,l);
end;
end; procedure work;
var
head,tail,x,y,i,j,too:longint;
begin
maxflow;
{ for i:=0 to m<<1 do
writeln(edge[i].from,' ',edge[i].toward,' ',edge[i].next,' ',edge[i].cap); }
head:=;
tail:=;
p[]:=s;
fillchar(chose1,sizeof(chose1),false);
chose1[s]:=true;
while head<=tail do begin
x:=p[head];
i:=first[x];
while i>= do begin
too:=edge[i].toward;
if (edge[i].cap>) and (not chose1[too]) then begin
inc(tail);
p[tail]:=too;
chose1[too]:=true;
end;
i:=edge[i].next;
end;
inc(head);
end;
//for i:= to n do writeln(i,' ',chose1[i]);
head:=;
tail:=;
p[]:=t;
fillchar(chose2,sizeof(chose2),false);
chose2[t]:=true;
while head<=tail do begin
x:=p[head];
i:=first[x];
while i>= do begin
too:=edge[i].toward;
if (edge[i xor ].cap>) and (not chose2[too]) then begin
inc(tail);
p[tail]:=too;
chose2[too]:=true;
end;
i:=edge[i].next;
end;
inc(head);
end;
//for i:= to n do writeln(i,' ',chose2[i]);
for i:= to m do begin
j:=(i-)<<;
if edge[j].cap> then begin
writeln(,' ',);
continue;
end;
x:=edge[j].from;
y:=edge[j].toward;
if not ( (chose1[x] and chose1[y]) or (chose2[x] and chose2[y]) )then write() else write();
write(' ');
if (chose1[x] and chose2[y]) or (chose1[y] and chose2[x])then writeln() else writeln();
end;
readln;
end; begin
into;
work;
end.
上一篇:(2016 年) githup 博客地址 : https://github.com/JMWY/MyBlog


下一篇:Malware Defender(HIPS主动防御软件) V2.8 免费版