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]

边表模板

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
     
      0 do        begin          if sid[pre[po]].cap
      
       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 
     
      #include 
      
       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]
       
        >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\n",ans);  }