program p1266;
type
bian=record
first,next,point,f,w,bo:longint;
end;
var
b:array[1..1000000] of bian;
p,d,dst:array[1..100000] of longint;
x:array[1..1000000] of longint;
pd:array[1..100000] of boolean;
k1,k2,k3,k4,len,i,j,n,m:longint;
procedure ade(k1,k2,k3,k4:longint);
begin
inc(len);
b[len].point:=k2;
b[len].next:=p[k1];
b[len].first:=k1;
b[len].w:=k3;
b[len].f:=k4;
p[k1]:=len;
end;
procedure add(k1,k2,k3,k4:longint);
begin
ade(k1,k2,k3,k4);
ade(k2,k1,k3,0);
end;
procedure spfa;
var
head,now,i,j:longint;
begin
fillchar(pd,sizeof(pd),false);
fillchar(x,sizeof(x),0);
fillchar(d,sizeof(d),$3f);
head:=1; now:=0; x[1]:=n; d[n]:=0; pd[n]:=true;
while head>now do begin
inc(now);
i:=p[x[now]];
while i<>-1 do begin
j:=b[i].point;
if d[j]>d[x[now]]+b[i].w then begin
d[j]:=d[x[now]]+b[i].w;
if pd[j]=false then begin
pd[j]:=true;
inc(head);
x[head]:=j;
end;
end;
i:=b[i].next;
end;
pd[x[now]]:=false;
end;
end;
procedure dfs(k:longint);
var
i,j:longint;
begin
pd[k]:=true;
if k=n then exit;
i:=p[k];
while i<>-1 do begin
j:=b[i].point;
if (d[j]+b[i].w=d[k]) and (b[i].f>0) then begin
b[i].bo:=1;
b[i xor 1].bo:=1;
if pd[j]=false then dfs(j);
end;
i:=b[i].next;
end;
end;
function min(k1,k2:longint):longint;
begin
if k1<k2 then exit(k1) else exit(k2);
end;
function bfs:boolean;
var
k1,k2,k3,now,head,i,j:longint;
begin
fillchar(pd,sizeof(pd),false);
pd[1]:=true; head:=1; now:=0; x[1]:=1; dst[1]:=0;
while now<head do begin
inc(now);
i:=p[x[now]];
while i>-1 do begin
k1:=b[i].point;
{writeln(k1,' ',b[i].f,' ',b[i].bo);
readln;}
if (pd[k1]=false) and (b[i].f>0) and (b[i].bo>0) then begin
pd[k1]:=true;
dst[k1]:=dst[x[now]]+1;
if k1=n then exit(true);
inc(head);
x[head]:=k1;
end;
i:=b[i].next;
end;
end;
exit(pd[n]);
end;
function change(k1,k2:longint):longint;
var
now,i,j,k:longint;
begin
if (k1=n) or (k2=0) then exit(k2);
now:=p[k1];
j:=0;
while now>-1 do begin
i:=b[now].point;
if (b[now].f>0) and (dst[k1]=dst[i]-1) and (b[now].bo>0) then begin
k:=change(i,min(b[now].f,k2));
k2:=k2-k;
j:=j+k;
b[now].f:=b[now].f-k;
inc(b[now xor 1].f,k);
if k2=0 then break;
end;
now:=b[now].next;
end;
if j=0 then dst[k1]:=-1;
exit(j);
end;
function dinic:longint;
var
num:longint;
begin
num:=0;
while bfs=true do begin
num:=num+change(1,maxlongint);
end;
exit(num);
end;
begin
readln(n,m);
len:=-1;
fillchar(p,sizeof(p),-1);
fillchar(b,sizeof(b),0);
for i:=1 to m do begin
readln(k1,k2,k3,k4);
add(k1,k2,k3,k4);
add(k2,k1,k3,k4);
end;
spfa;
writeln(d[1]);
{for i:=1 to n do
write(d[i],' ');
writeln;}
fillchar(pd,sizeof(pd),false);
dfs(1);
{for i:=1 to len do
writeln(b[i].first,' ',b[i].point,' ',b[i].w,' ',b[i].bo,' ',b[i].f);}
writeln(dinic);
end.
先做一次SPFA，然后就可以求出家到学校的最短路图（由所有最短路构成的图），在这个图上做最小割，流量为C，答案就是正解。
2022年8月16日 02:50
Every year, this board administers the 11th grade test, and the Maha 11th Important Question Paper for this examination will soon be available on the Maharashtra Board's official website. Around 15 lakh students took part in the Maharashtra Board Class 11th examinations, which were likewise held in the month of February starting in March 2023. Maha 11th Model Paper 2023 The Maharashtra Board Class 11th Important Question Paper 2023 was released in the month of May 2023. According to a poll, Maharashtra 11th Important Question Paper 2023 is expected to be released in May of this year as well. We advise all students to be patient and wait for the release of the Important Question Paper 2023.