bzoj1834 最大流+最小费用最大流

就当模板啦…
不过这题第二问的构图还是可以想一下的。。。
在残量网络中把原来的边全部加一遍，但是有费用w，容量无限大，一开始的边还是费用为0
新建一个源点s，s向1连一条边，容量为k，费用为0，保证这条边满流，就有最小费用了。

program bzoj1834;
type point=records,t,cap,flow,o,w,next:longint;
end;
var p,l,n,m,k,c,i:longint;v1:array[0..1010]of boolean;edge:array[1..30010]of point;head,d:array[0..1010]of longint;b:array[1..10000000]of longint;u,v,w:array[0..5010]of longint;
procedure add(u,v,c,w:longint);
beginl:=l+1;edge[l].s:=u;edge[l].t:=v;edge[l].cap:=c;edge[l].flow:=0;edge[l].o:=l+1;edge[l].w:=w;//费用edge[l].next:=head[u];head[u]:=l;l:=l+1;edge[l].s:=v;edge[l].t:=u;edge[l].cap:=c;edge[l].flow:=c;edge[l].o:=l-1;edge[l].w:=-w;edge[l].next:=head[v];head[v]:=l;
end;
function min(a,b:longint):longint;
beginif athen min:=a else min:=b;
end;function bfs:boolean;
var top,tail,p:longint;
begind[1]:=1;top:=1;tail:=1;b[1]:=1;fillchar(v1,sizeof(v1),false);v1[1]:=true;repeatp:=head[b[top]];while p<>-1 dobeginif (v1[edge[p].t]=false)and(edge[p].cap>edge[p].flow) thenbeginv1[edge[p].t]:=true;d[edge[p].t]:=d[b[top]]+1;//层次tail:=tail+1;b[tail]:=edge[p].t;end;p:=edge[p].next;end;top:=top+1;until top>tail;exit(v1[n]);
end;function addflow(x,maxflow:longint):longint;
var p,o:longint;
beginif (x=n) or (maxflow=0) then exit(maxflow);addflow:=0;//这个一定要写！！p:=head[x];while p<>-1 dobeginif (d[edge[p].t]=d[x]+1)and(edge[p].cap>edge[p].flow) thenbegino:=addflow(edge[p].t,min(maxflow,edge[p].cap-edge[p].flow));if o>0 thenbegininc(edge[p].flow,o);dec(edge[edge[p].o].flow,o);maxflow:=maxflow-o;addflow:=addflow+o;if maxflow=0 then break;end;end;p:=edge[p].next;end;
end;function dinic:longint;
begindinic:=0;while bfs dodinic:=dinic+addflow(1,maxlongint);
end;function spfa:longint;
var cost,top,tail,i,p:longint;pre,re:array[0..1010]of longint;flag:array[0..1010]of boolean;d:array[0..1010]of longint;mm:longint;
begincost:=0;while true dobegintop:=1;tail:=1;b[1]:=0;for i:=0 to n do d[i]:=maxlongint;d[0]:=0;//流量fillchar(pre,sizeof(pre),0);pre[0]:=-1;fillchar(re,sizeof(re),0);fillchar(flag,sizeof(flag),true);flag[0]:=false;repeatp:=head[b[top]];while p<>-1 dobeginif (edge[p].cap>edge[p].flow)and(d[b[top]]+edge[p].wthenbegind[edge[p].t]:=d[b[top]]+edge[p].w;pre[edge[p].t]:=b[top];re[edge[p].t]:=p;if flag[edge[p].t] thenbeginflag[edge[p].t]:=false;tail:=tail+1;b[tail]:=edge[p].t;end;end;p:=edge[p].next;end;flag[b[top]]:=true;top:=top+1;until top>tail;if d[n]=maxlongint then break;i:=n;mm:=maxlongint;while pre[i]<>-1 dobeginmm:=min(mm,edge[re[i]].cap-edge[re[i]].flow);i:=pre[i];end;i:=n;while pre[i]<>-1 dobegininc(edge[re[i]].flow,mm);dec(edge[edge[re[i]].o].flow,mm);cost:=cost+mm*edge[re[i]].w;i:=pre[i];end;end;spfa:=cost;
end;
beginread(n,m,k);for i:=0 to n do head[i]:=-1;for i:=1 to m dobeginread(u[i],v[i],c,w[i]);add(u[i],v[i],c,0);end;write(dinic,' ');//最小费用最大流for i:=1 to m doadd(u[i],v[i],maxlongint,w[i]);add(0,1,k,0);writeln(spfa);readln;readln;
end.

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！