但是可能有自环且这个环也有权值，这样子虽然SPFA还是跑的出来（先把有自环的u搞出来，然后松弛的时候由于还在队列中就不加入队列了，所以跑的出来），但是咱的模板中用于回溯修改残余网络的pre数组就会把u的pre记作本身u，这样子回溯的时候就是死循环了。所以从这题可以看出模板需要改进了....咱们可以不另开pre数组，把它的pre直接存在边上，然后对于t再存一个从哪条边松弛过来的即可（感觉不优美了...)，所以先上个代码...待思考解决这个问题...
program flow22;
const maxn=100000;
type edges=record
u,v,w,c,pre:longint;
end;
point=record
x,y:longint;
end;
var e:array[0..maxn]of edges;
last,low,pre,d,que,w,cir:array[0..maxn]of longint;
v:array[0..maxn]of boolean;
x,y:array[0..maxn]of point;
tot,cost,n,limit,num:longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
procedure addedge(u,v,w,c:longint);
begin
inc(tot);
e[tot].u:=u;
e[tot].v:=v;
e[tot].w:=w;
e[tot].c:=c;
e[tot].pre:=last[u];
last[u]:=tot;
inc(tot);
e[tot].u:=v;
e[tot].v:=u;
e[tot].w:=0;
e[tot].c:=-c;
e[tot].pre:=last[v];
last[v]:=tot;
end;
function spfa(s,t:longint):boolean;
var u,tmp,aug,l,r:longint;
begin
fillchar(v,sizeof(v),false);
fillchar(pre,sizeof(pre),0);
fillchar(d,sizeof(d),254);
fillchar(low,sizeof(low),0);
fillchar(que,sizeof(que),0);
l:=0;r:=1;que[l]:=s;
v[s]:=true;d[s]:=0;
low[s]:=maxlongint;
low[t]:=low[s];
while l<>r do
begin
u:=que[l];
tmp:=last[u];
v[u]:=false;
while tmp<>-1 do
begin
if (d[e[tmp].v]<d[u]+e[tmp].c)and(e[tmp].w>0) then
begin
d[e[tmp].v]:=d[u]+e[tmp].c;
pre[e[tmp].v]:=tmp;
low[e[tmp].v]:=min(low[u],e[tmp].w);
if not v[e[tmp].v] then
begin
que[r]:=e[tmp].v;
r:=(r+1)mod maxn;
v[e[tmp].v]:=true;
end;
end;
tmp:=e[tmp].pre;
end;
l:=(l+1)mod maxn;
end;
if low[t]=maxlongint then exit(false);
cost:=cost+low[t]*d[t];
u:=t;aug:=low[t];
while u<>s do
begin
dec(e[pre[u]].w,aug);
inc(e[pre[u] xor 1].w,aug);
u:=e[pre[u]].u;
end;
exit(true);
end;
procedure qsort(l,r:longint);
var i,j,x,y:longint;
begin
i:=l;j:=r;
x:=w[(l+r)shr 1];
repeat
while w[i]<x do inc(i);
while w[j]>x do dec(j);
if i<=j then
begin
y:=w[i];w[i]:=w[j];w[j]:=y;
inc(i);dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if j>l then qsort(l,j);
end;
procedure prepare;
var i:longint;
begin
qsort(1,n shl 1);
num:=1;
for i:=2 to n shl 1 do
if w[i]<>w[num] then
begin
inc(num);
w[num]:=w[i];
end;
end;
function find(a:longint):longint;
var l,r,mid:longint;
begin
l:=1;r:=num;
while l<>r do
begin
mid:=(l+r)shr 1;
if w[mid]=a then exit(mid);
if w[mid]<a then l:=mid+1
else r:=mid-1;
end;
exit(l);
end;
function dist(u,v,w,x:longint):longint;
begin
exit(trunc(sqrt((u-w)*(u-w)+(v-x)*(v-x))));
end;
procedure init;
var i:longint;
begin
read(n,limit);
for i:=1 to n do
begin
read(x[i].x,x[i].y,y[i].x,y[i].y);
w[i shl 1-1]:=x[i].x;
w[i shl 1]:=y[i].x;
end;
prepare;
fillchar(last,sizeof(last),255);
tot:=-1;
addedge(0,1,limit,0);
addedge(num,num+1,limit,0);
for i:=2 to num do
addedge(i-1,i,maxlongint shr 1,0);
for i:=1 to n do
addedge(find(x[i].x),find(y[i].x),1,dist(x[i].x,x[i].y,y[i].x,y[i].y));
cost:=0;
while spfa(0,num+1) do;
write(cost);
end;
begin
init;
end.
评论