题意：n个点，m条无向边，每条边有一个容量和扩容费用（容量扩大1的费用），2个询问：（1）不扩容下的1~N最大流 （2）将最大流增加K的最小费用
强行凑出的网络流经典题么 23333
对于第一问，裸跑最大流即可
第二问的建图还是很不错的，
一开始认为,应该重新建边，容量为K，费用是给题目给的。
but，too young too simple，always naive
因为会出现问题：在残留网络中仍有流量，这些流量扩到新的最大流里是不需要费用的
所以，我们在第一问建图时，费用设为0（解决了不需要费用的问题）
然后在跑完第一问后，再重新建边 x -> y 容量为正无穷（表示这条边可以一直扩容） 费用为给定费用
然后再跑费用流
注意：第一问的最大流为ans，要求增加K，但我们重现连新边后所得的最大流 比 （ans+k）大，这肯定不是最优的（因为你扩了不用扩的）。为了保证第二问增加的流量为K，我们可以在1号或n号点加一条边，容量为k 费用为0，用来限流，使增加的不超过k
注意对应数组的范围，mdzz，开小了改了好久
var n,m,k,ans,l :longint; z,ss,st :longint; i :longint; vis :array[0..1010] of boolean; x,y,cc :array[0..5010] of longint; last,que,dis :array[0..1010] of longint; father :array[0..1010] of longint; pre,other,len,c :array[0..21010] of longint; function min(a,b:Longint):longint; begin if a<b then exit(a) else exit(b); end; procedure connect(x,y,z,cost:longint); begin inc(l); pre[l]:=last[x]; last[x]:=l; other[l]:=y; len[l]:=z; c[l]:=cost; end; function spfa:boolean; var i,h,tl,cur,p,q:longint; begin for i:=1 to st do dis[i]:=maxlongint div 10; h:=0; tl:=1; que[1]:=ss; dis[ss]:=0; while (h<>tl) do begin h:=h mod 1005+1; cur:=que[h]; vis[cur]:=false; q:=last[cur]; while (q<>0) do begin p:=other[q]; if (dis[p]>dis[cur]+c[q]) and (len[q]>0) then begin dis[p]:=dis[cur]+c[q]; father[p]:=q; if not vis[p] then begin tl:=tl mod 1005+1; que[tl]:=p; vis[p]:=true; end; end; q:=pre[q]; end; end; if dis[st]=maxlongint div 10 then exit(false) else exit(true); end; procedure update; var cur,low:longint; begin low:=maxlongint; cur:=st; while (cur<>ss) do begin low:=min(low,len[father[cur]]); cur:=other[father[cur] xor 1]; end; cur:=st; while (cur<>ss) do begin dec(len[father[cur]],low); inc(len[father[cur] xor 1],low); inc(ans,low*c[father[cur]]); cur:=other[father[cur] xor 1]; end; end; function bfs:boolean; var p,q,cur,h,tl:longint; begin fillchar(dis,sizeof(dis),0); h:=0; tl:=1; que[1]:=ss; dis[ss]:=1; while (h<>tl) do begin h:=h mod 1005+1; cur:=que[h]; q:=last[cur]; while (q<>0) do begin p:=other[q]; if (dis[p]=0) and (len[q]>0) then begin dis[p]:=dis[cur]+1; tl:=tl mod 1005+1; que[tl]:=p; if p=st then exit(true); end; q:=pre[q]; end; end; exit(false); end; function dinic(x,flow:longint):longint; var p,q,tt,rest:longint; begin if x=st then exit(flow); rest:=flow; q:=last[x]; while (q<>0) do begin p:=other[q]; if (dis[p]=dis[x]+1) and (len[q]>0) and (rest>0) then begin tt:=dinic(p,min(len[q],rest)); dec(len[q],tt); dec(rest,tt); inc(len[q xor 1],tt); if rest=0 then exit(flow); end; q:=pre[q]; end; if rest=flow then dis[x]:=0; exit(flow-rest); end; begin read(n,m,k); ss:=1; st:=n; l:=1; for i:=1 to m do begin read(x[i],y[i],z,cc[i]); connect(x[i],y[i],z,0); connect(y[i],x[i],0,0); //writeln(l); end; ans:=0; while bfs do inc(ans,dinic(ss,maxlongint div 10)); // write(ans,' '); for i:=1 to m do begin connect(x[i],y[i],maxlongint div 10,cc[i]); connect(y[i],x[i],0,-cc[i]); end; ss:=1; st:=n+1; connect(n,st,k,0); connect(st,n,0,0); // ans:=0; while spfa do update; writeln(ans); end. ——by Eirlys
