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=;sid[cnt].cos=-cos;sid[cnt].next=nd[to];nd[to]=cnt++;
}
int spfa(){
dl[head=tail=]=sor;
for (int i=;i<=n+;i++) dis[i]=1e9;
for (int i=;i<=n+;i++) b[i]=;
for (int i=;i<=n+;i++) count[i]=;
b[sor]=;
dis[sor]=;
while (head<=tail){
for (int p=nd[dl[head]];p!=-;p=sid[p].next)
if ((sid[p].cap!=)&&(dis[sid[p].des]>dis[dl[head]]+sid[p].cos)){
path[sid[p].des]=p;
if (b[sid[p].des]==){
dl[++tail]=sid[p].des;
b[sid[p].des]=;
count[sid[p].des]++;
}
dis[sid[p].des]=dis[dl[head]]+sid[p].cos;
}
b[dl[head++]]=;
}
if (dis[tar]==1e9) return();else return();
}
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^].cap+=flow;
po=sid[p].fr;
}
}
最小费用最大流
uses math; var
n,m,i,j :longint;
ans:int64;
dl:array[..] of longint;
cost,tcap,cap:array[..,..] of int64;
dis:array[..] of longint;
pre:array[..] of longint;
a,b:array[..] of longint;
c:Array[..,..] of longint; procedure build;
var
i,j:longint;
begin
for i:= to n do
begin
cap[,i]:=maxlongint;
cost[,i]:=;
end; for i:= to n do
begin
cap[i,i+n]:=a[i];
cost[i,i+n]:=;
end; for i:= to n do
for j:= to m do
begin
cap[i+n,j+*n]:=maxlongint;
cost[i+n,j+*n]:=c[i,j];
cost[j+*n,i+n]:=-c[i,j];
end; for i:= to m do
begin
cap[i+*n,i+*n+m]:=b[i];
cost[i+*n,i+*n+m]:=;
end; for i:= to m do
begin
cap[i+*n+m,*n+*m+]:=maxlongint;
cost[i+*n+m,*n+*m+]:=;
end;
end; procedure aug;
var
po:longint;
mi:int64;
pr:longint;
begin
po:=*n+*m+;
mi:=maxlongint;
while po<> do
begin
pr:=pre[po];
mi:=min(mi,tcap[pr,po]);
po:=pr;
end; po:=*n+*m+;
while po<> 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:= to *m+*n+ do
dis[i]:=maxlongint;
dis[]:=; head:=;tail:=;
dl[]:=;
while head<=tail do
begin
u:=dl[head];
for i:= to *n+*m+ do
if (tcap[u,i]>) 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[*n+*m+]=maxlongint then exit(false) else exit(true);
end; begin read(n,m); for i:= to n do
read(a[i]);
for i:= to m do
read(b[i]);
for i:= to n do
for j:= to m do
read(c[i,j]); build; for i:= to *n+*m+ do
for j:= to *n+*m+ 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[..] of longint;
cost,tcap,cap:array[..,..] of int64;
dis:array[..] of longint;
pre:array[..] of longint;
a,b:array[..] of longint;
c:Array[..,..] of longint; procedure build;
var
i,j:longint;
begin
for i:= to n do
begin
cap[,i]:=maxlongint;
cost[,i]:=;
end; for i:= to n do
begin
cap[i,i+n]:=a[i];
cost[i,i+n]:=;
end; for i:= to n do
for j:= to m do
begin
cap[i+n,j+*n]:=maxlongint;
cost[i+n,j+*n]:=c[i,j];
cost[j+*n,i+n]:=-c[i,j];
end; for i:= to m do
begin
cap[i+*n,i+*n+m]:=b[i];
cost[i+*n,i+*n+m]:=;
end; for i:= to m do
begin
cap[i+*n+m,*n+*m+]:=maxlongint;
cost[i+*n+m,*n+*m+]:=;
end;
end; procedure aug;
var
po:longint;
mi:int64;
pr:longint;
begin
po:=*n+*m+;
mi:=maxlongint;
while po<> do
begin
pr:=pre[po];
mi:=min(mi,tcap[pr,po]);
po:=pr;
end; po:=*n+*m+;
while po<> 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:= to *m+*n+ do
dis[i]:=-maxlongint;
dis[]:=; head:=;tail:=;
dl[]:=;
while head<=tail do
begin
u:=dl[head];
for i:= to *n+*m+ do
if (tcap[u,i]>) 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[*n+*m+]=-maxlongint then exit(false) else exit(true);
end; begin read(n,m); for i:= to n do
read(a[i]);
for i:= to m do
read(b[i]);
for i:= to n do
for j:= to m do
read(c[i,j]); build; ans:=;
for i:= to *n+*m+ do
for j:= to *n+*m+ 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:=;
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:= to n+ do dis[i]:=maxlongint div ;
for i:= to n+ do vis[i]:=true; head:=;tail:=;
dl[]:=;
while head<=tail do
begin
u:=dl[head];
p:=nd[dl[head]];
while p<>- do
begin
if (sid[p].cap>) 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+]=maxlongint div then exit(false) else exit(true);
end; procedure aug;
var
po,mi:longint;
begin
po:=n+;
mi:=maxlongint;
while po<> do
begin
if sid[pre[po]].cap<mi then mi:=sid[pre[po]].cap;
po:=sid[pre[po]].u;
end; po:=n+;
while po<> do
begin
inc(ans,mi*sid[pre[po]].cost);
dec(sid[pre[po]].cap,mi);
inc(sid[pre[po] xor ].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[]; struct treenode{
int l,r,lc,rc;
}tr[]; int cnt,nd[],dl[],head,tail,sor,tar,dis[],b[],path[],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=;sid[scnt].cos=-cos;sid[scnt].next=nd[to];nd[to]=scnt++;
} int spfa(){
dl[head=tail=]=sor;
for (int i=;i<=tar;i++) dis[i]=,b[i]=;
b[sor]=;
dis[sor]=;
while (head<=tail){
for (int p=nd[dl[head]];p!=-;p=sid[p].next)
if ((sid[p].cap!=)&&(dis[sid[p].des]<dis[dl[head]]+sid[p].cos)){
path[sid[p].des]=p;
if (b[sid[p].des]==){
dl[++tail]=sid[p].des;
b[sid[p].des]=;
}
dis[sid[p].des]=dis[dl[head]]+sid[p].cos;
}
b[dl[head++]]=;
} if (dis[tar]==) return();else return();
} 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^].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,,);return;} int t=cnt,mid=(l+r)>>;
tr[t].lc=cnt+;addedge(t,cnt+,1e9,);
build(l,mid);
tr[t].rc=cnt+;addedge(t,cnt+,1e9,);
build(mid+,r);
} void query(int po,int l,int r,int fr){
if (tr[po].l==l&&tr[po].r==r){
addedge(fr,po,1e9,);return;
} int mid=(tr[po].l+tr[po].r)>>;
if (l<=mid) query(tr[po].lc,l,min(mid,r),fr);
if (r>mid) query(tr[po].rc,max(mid+,l),r,fr);
} int main(){
int n,t1,t2,t3;
scanf("%d",&n);
sor=;tar=;
for (int i=sor;i<=tar;i++) nd[i]=-;
build(,); for (int i=;i<=n;i++){
scanf("%d%d%d",&t1,&t2,&t3);t2--;
addedge(sor,++cnt,,t3);
query(,t1,t2,cnt);
} while (spfa())
aug(); printf("%d\n",ans);
}