void addedge(int fr,int to,int cap,int cos){ sid[cnt].fr=fr;sid[cnt].des=to;sid[cnt].cap=cap;sid[cnt].cos=cos;sid[cnt].next=nd[fr];nd[fr]=cnt++; sid[cnt].fr=to;sid[cnt].des=fr;sid[cnt].cap=0;sid[cnt].cos=-cos;sid[cnt].next=nd[to];nd[to]=cnt++; } int spfa(){ dl[head=tail=1]=sor; for (int i=1;i<=n+2;i++) dis[i]=1e9; for (int i=0;i<=n+2;i++) b[i]=0; for (int i=0;i<=n+2;i++) count[i]=0; b[sor]=1; dis[sor]=0; while (head<=tail){ for (int p=nd[dl[head]];p!=-1;p=sid[p].next) if ((sid[p].cap!=0)&&(dis[sid[p].des]>dis[dl[head]]+sid[p].cos)){ path[sid[p].des]=p; if (b[sid[p].des]==0){ dl[++tail]=sid[p].des; b[sid[p].des]=1; count[sid[p].des]++; } dis[sid[p].des]=dis[dl[head]]+sid[p].cos; } b[dl[head++]]=0; } if (dis[tar]==1e9) return(0);else return(1); } void aug(){ int po=tar,flow=1e9; while (po!=sor){ int p=path[po]; flow=min(flow,sid[p].cap); po=sid[p].fr; } po=tar; while (po!=sor){ int p=path[po]; sid[p].cap-=flow; ans+=flow*sid[p].cos; sid[p^1].cap+=flow; po=sid[p].fr; } }
最小费用最大流
uses math; var n,m,i,j :longint; ans:int64; dl:array[1..50000] of longint; cost,tcap,cap:array[0..501,0..501] of int64; dis:array[0..501] of longint; pre:array[0..501] of longint; a,b:array[1..250] of longint; c:Array[1..250,1..250] of longint; procedure build; var i,j:longint; begin for i:=1 to n do begin cap[0,i]:=maxlongint; cost[0,i]:=0; end; for i:=1 to n do begin cap[i,i+n]:=a[i]; cost[i,i+n]:=0; end; for i:=1 to n do for j:=1 to m do begin cap[i+n,j+2*n]:=maxlongint; cost[i+n,j+2*n]:=c[i,j]; cost[j+2*n,i+n]:=-c[i,j]; end; for i:=1 to m do begin cap[i+2*n,i+2*n+m]:=b[i]; cost[i+2*n,i+2*n+m]:=0; end; for i:=1 to m do begin cap[i+2*n+m,2*n+2*m+1]:=maxlongint; cost[i+2*n+m,2*n+2*m+1]:=0; end; end; procedure aug; var po:longint; mi:int64; pr:longint; begin po:=2*n+2*m+1; mi:=maxlongint; while po<>0 do begin pr:=pre[po]; mi:=min(mi,tcap[pr,po]); po:=pr; end; po:=2*n+2*m+1; while po<>0 do begin pr:=pre[po]; dec(tcap[pr,po],mi); inc(tcap[po,pr],mi); inc(ans,mi*cost[pr,po]); po:=pr; end; end; function spfa1:boolean; var i,head,tail,u:longint; begin for i:=1 to 2*m+2*n+1 do dis[i]:=maxlongint; dis[0]:=0; head:=1;tail:=1; dl[1]:=0; while head<=tail do begin u:=dl[head]; for i:=0 to 2*n+2*m+1 do if (tcap[u,i]>0) and (dis[i]>dis[u]+cost[u,i]) then begin pre[i]:=u; inc(tail); dl[tail]:=i; dis[i]:=dis[u]+cost[u,i]; end; inc(head); end; if dis[2*n+2*m+1]=maxlongint then exit(false) else exit(true); end; begin read(n,m); for i:=1 to n do read(a[i]); for i:=1 to m do read(b[i]); for i:=1 to n do for j:=1 to m do read(c[i,j]); build; for i:=0 to 2*n+2*m+1 do for j:=0 to 2*n+2*m+1 do tcap[i,j]:=cap[i,j]; while spfa1 do aug; writeln(ans); end.
最大费用最大流
uses math; var n,m,i,j :longint; ans:int64; dl:array[1..50000] of longint; cost,tcap,cap:array[0..501,0..501] of int64; dis:array[0..501] of longint; pre:array[0..501] of longint; a,b:array[1..250] of longint; c:Array[1..250,1..250] of longint; procedure build; var i,j:longint; begin for i:=1 to n do begin cap[0,i]:=maxlongint; cost[0,i]:=0; end; for i:=1 to n do begin cap[i,i+n]:=a[i]; cost[i,i+n]:=0; end; for i:=1 to n do for j:=1 to m do begin cap[i+n,j+2*n]:=maxlongint; cost[i+n,j+2*n]:=c[i,j]; cost[j+2*n,i+n]:=-c[i,j]; end; for i:=1 to m do begin cap[i+2*n,i+2*n+m]:=b[i]; cost[i+2*n,i+2*n+m]:=0; end; for i:=1 to m do begin cap[i+2*n+m,2*n+2*m+1]:=maxlongint; cost[i+2*n+m,2*n+2*m+1]:=0; end; end; procedure aug; var po:longint; mi:int64; pr:longint; begin po:=2*n+2*m+1; mi:=maxlongint; while po<>0 do begin pr:=pre[po]; mi:=min(mi,tcap[pr,po]); po:=pr; end; po:=2*n+2*m+1; while po<>0 do begin pr:=pre[po]; dec(tcap[pr,po],mi); inc(tcap[po,pr],mi); inc(ans,mi*cost[pr,po]); po:=pr; end; end; function spfa2:boolean; var i,u,head,tail:longint; begin for i:=1 to 2*m+2*n+1 do dis[i]:=-maxlongint; dis[0]:=0; head:=1;tail:=1; dl[1]:=0; while head<=tail do begin u:=dl[head]; for i:=0 to 2*n+2*m+1 do if (tcap[u,i]>0) and (dis[i]<dis[u]+cost[u,i]) then begin pre[i]:=u; inc(tail); dl[tail]:=i; dis[i]:=dis[u]+cost[u,i]; end; inc(head); end; if dis[2*n+2*m+1]=-maxlongint then exit(false) else exit(true); end; begin read(n,m); for i:=1 to n do read(a[i]); for i:=1 to m do read(b[i]); for i:=1 to n do for j:=1 to m do read(c[i,j]); build; ans:=0; for i:=0 to 2*n+2*m+1 do for j:=0 to 2*n+2*m+1 do tcap[i,j]:=cap[i,j]; while spfa2 do aug; writeln(ans); end.
边表模板
procedure addedge(u,v,cap,cost:longint); begin sid[tot].u:=u; sid[tot].v:=v; sid[tot].cap:=cap; sid[tot].cost:=cost; sid[tot].next:=nd[u]; nd[u]:=tot; inc(tot); sid[tot].u:=v; sid[tot].v:=u; sid[tot].cap:=0; sid[tot].cost:=-cost; sid[tot].next:=nd[v]; nd[v]:=tot; inc(tot); end; function spfa:boolean; var i,head,tail,u,p:longint; begin for i:=1 to n+1 do dis[i]:=maxlongint div 2; for i:=1 to n+1 do vis[i]:=true; head:=1;tail:=1; dl[1]:=0; while head<=tail do begin u:=dl[head]; p:=nd[dl[head]]; while p<>-1 do begin if (sid[p].cap>0) and (dis[u]+sid[p].cost<dis[sid[p].v]) then begin if vis[sid[p].v]=true then begin inc(tail); dl[tail]:=sid[p].v; vis[sid[p].v]:=false; end; pre[sid[p].v]:=p; dis[sid[p].v]:=dis[u]+sid[p].cost; end; p:=sid[p].next; end; vis[dl[head]]:=true; inc(head); end; if dis[n+1]=maxlongint div 2 then exit(false) else exit(true); end; procedure aug; var po,mi:longint; begin po:=n+1; mi:=maxlongint; while po<>0 do begin if sid[pre[po]].cap<mi then mi:=sid[pre[po]].cap; po:=sid[pre[po]].u; end; po:=n+1; while po<>0 do begin inc(ans,mi*sid[pre[po]].cost); dec(sid[pre[po]].cap,mi); inc(sid[pre[po] xor 1].cap,mi); po:=sid[pre[po]].u; end; end;
-----------------------------------------------------------------------------------------
BZOJ4276
用线段树优化费用流
#include <cstdio> #include <iostream> using namespace std; struct edge{ int fr,des,cap,cos,next; }sid[400001]; struct treenode{ int l,r,lc,rc; }tr[20001]; int cnt,nd[40001],dl[4000001],head,tail,sor,tar,dis[40001],b[40001],path[40001],ans,scnt; void addedge(int fr,int to,int cap,int cos){ sid[scnt].fr=fr;sid[scnt].des=to;sid[scnt].cap=cap;sid[scnt].cos=cos;sid[scnt].next=nd[fr];nd[fr]=scnt++; sid[scnt].fr=to;sid[scnt].des=fr;sid[scnt].cap=0;sid[scnt].cos=-cos;sid[scnt].next=nd[to];nd[to]=scnt++; } int spfa(){ dl[head=tail=1]=sor; for (int i=1;i<=tar;i++) dis[i]=0,b[i]=0; b[sor]=1; dis[sor]=0; while (head<=tail){ for (int p=nd[dl[head]];p!=-1;p=sid[p].next) if ((sid[p].cap!=0)&&(dis[sid[p].des]<dis[dl[head]]+sid[p].cos)){ path[sid[p].des]=p; if (b[sid[p].des]==0){ dl[++tail]=sid[p].des; b[sid[p].des]=1; } dis[sid[p].des]=dis[dl[head]]+sid[p].cos; } b[dl[head++]]=0; } if (dis[tar]==0) return(0);else return(1); } void aug(){ int po=tar,flow=1e9; while (po!=sor){ int p=path[po]; flow=min(flow,sid[p].cap); po=sid[p].fr; } po=tar; while (po!=sor){ int p=path[po]; sid[p].cap-=flow; ans+=flow*sid[p].cos; sid[p^1].cap+=flow; po=sid[p].fr; } } void build(int l,int r){ tr[++cnt].l=l;tr[cnt].r=r; if (l==r) {addedge(cnt,tar,1,0);return;} int t=cnt,mid=(l+r)>>1; tr[t].lc=cnt+1;addedge(t,cnt+1,1e9,0); build(l,mid); tr[t].rc=cnt+1;addedge(t,cnt+1,1e9,0); build(mid+1,r); } void query(int po,int l,int r,int fr){ if (tr[po].l==l&&tr[po].r==r){ addedge(fr,po,1e9,0);return; } int mid=(tr[po].l+tr[po].r)>>1; if (l<=mid) query(tr[po].lc,l,min(mid,r),fr); if (r>mid) query(tr[po].rc,max(mid+1,l),r,fr); } int main(){ int n,t1,t2,t3; scanf("%d",&n); sor=0;tar=30001; for (int i=sor;i<=tar;i++) nd[i]=-1; build(1,5000); for (int i=1;i<=n;i++){ scanf("%d%d%d",&t1,&t2,&t3);t2--; addedge(sor,++cnt,1,t3); query(1,t1,t2,cnt); } while (spfa()) aug(); printf("%d ",ans); }