bzoj2561

时间:2022-05-22 08:39:26

对于新加入的边,必须要既可能在最小生成树上也可能在最大生成树上
我们先对于最小生成树考虑
根据kruskal的理论,不难发现,u--v 长度为L的边可能出现在最小生成树上
就是说删边剩下的比L小的边一定不能使u,v连通,
因此问题就转化为求u,v两点的最小割了
最大生成树同理,最后答案是两个加起来

 const inf=;
type node=record
point,next,flow:longint;
end; var edge:array[..] of node;
cur,p,h,numh,pre,d:array[..] of longint;
x,y,z:array[..] of longint;
i,len,u,v,l,ans,n,m:longint; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure add(x,y,z:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].flow:=z;
edge[len].next:=p[x];
p[x]:=len;
end; function sap(s,t:longint):longint;
var u,i,j,q,tmp,neck:longint;
begin
for i:= to n do
cur[i]:=i;
fillchar(numh,sizeof(numh),);
fillchar(h,sizeof(h),);
u:=s;
h[s]:=;
numh[]:=n;
neck:=inf;
sap:=;
while h[s]<n do
begin
d[u]:=neck;
i:=cur[u];
while i<>- do
begin
j:=edge[i].point;
if (edge[i].flow>) and (h[u]=h[j]+) then
begin
cur[u]:=i;
pre[j]:=u;
neck:=min(neck,edge[i].flow);
u:=j;
if u=t then
begin
sap:=sap+neck;
while u<>s do
begin
u:=pre[u];
j:=cur[u];
dec(edge[j].flow,neck);
inc(edge[j xor ].flow,neck);
end;
neck:=inf;
end;
break;
end;
i:=edge[i].next;
end;
if i=- then
begin
dec(numh[h[u]]);
if numh[h[u]]= then exit;
q:=-;
tmp:=n;
i:=p[u];
while i<>- do
begin
j:=edge[i].point;
if (edge[i].flow>) then
if h[j]<tmp then
begin
tmp:=h[j];
q:=i;
end;
i:=edge[i].next;
end;
cur[u]:=q;
h[u]:=tmp+;
inc(numh[h[u]]);
if u<>s then
begin
u:=pre[u];
neck:=d[u];
end;
end;
end;
end; begin
readln(n,m);
for i:= to m do
readln(x[i],y[i],z[i]);
readln(u,v,l);
fillchar(p,sizeof(p),);
len:=-;
for i:= to m do
if z[i]>l then
begin
add(x[i],y[i],);
add(y[i],x[i],);
add(y[i],x[i],);
add(x[i],y[i],);
end;
ans:=sap(u,v); fillchar(p,sizeof(p),);
len:=-;
for i:= to m do
if z[i]<l then
begin
add(x[i],y[i],);
add(y[i],x[i],);
add(y[i],x[i],);
add(x[i],y[i],);
end;
ans:=ans+sap(u,v);
writeln(ans);
end.