wikioi1034 家园

这是一道神奇的网络流。具体详细的题解以及代码可以去Orz这个大神的博客。

传送门：

  简单地说，就是要建立一个模型，就是把每个点（包括地球和月球）都分成无数多个点……比如第j个时刻的地球，就用地球i号表示，第i个中转站就用i中转站j表示。（处理是把月球-1自动改为n+1吧）。把飞船看成是边。然后就是神奇的跑一遍sap看是否能运那么多人，不行再扩展一层节点在跑一遍……orz语言能力不好还是去看上面那个大神的博客吧。最后把数组开大！把记录边的数组开到很大很大……不然就和我一样wa了好多好多次……或者把time控制小一点……比如等于100是就不要找了根本找不到的，这样时间差不多就剩下100ms（time为200要跑700ms）……

type  arr=record    toward,cap,next:longint;  end;var  edge:array[0..100000]of arr;  d,num,first,cur,h:array[0..5000]of longint;  c:array[0..50,0..10000]of longint;  ss,tot,sum,st,s,t,i,j,k,n,m,kk,time,flow,leftk:longint;function cal(i,j:longint):longint;beginexit((n*2)*j+i+2);end;function min(x,y:longint):longint;beginif x>y then exit(y);exit(x);end;procedure add(i,j,k:longint);begin  edge[tot].toward:=j;  edge[tot].cap:=k;  edge[tot].next:=first[i];  first[i]:=tot;inc(tot);end;procedure addedge(i,j,k:longint);beginadd(i,j,k);add(j,i,0);end;function sap(v,flow:longint):longint;var  rec,ret,i,j:longint;beginif v=st then exit(flow);  rec:=0;  i:=cur[v];  while i<>-1 do begin    j:=edge[i].toward;    if (edge[i].cap>0) and (d[v]=d[j]+1) then begin      ret:=sap(j,min(flow-rec,edge[i].cap));      dec(edge[i].cap,ret);      inc(edge[i xor 1].cap,ret);      cur[v]:=i;      inc(rec,ret);      if rec=flow then exit(flow);    end;    i:=edge[i].next;  end;  dec(num[d[v]]);  if num[d[v]]=0 then d[ss]:=sum;  inc(d[v]);  inc(num[d[v]]);  cur[v]:=first[v];exit(rec);end;function maxflow:longint;var  flow:longint;beginfillchar(num,sizeof(num),0);  fillchar(d,sizeof(d),0);  for i:=0 to sum do cur[i]:=first[i];  num[0]:=sum;  flow:=0;  while d[ss]
      
       0 then begin    for i:=s to n do addedge(cal(i,time-1),cal(i,time),maxlongint);    addedge(cal(t,time-1),cal(t,time),maxlongint);    for i:=1 to m do begin      j:=time mod c[i,0]+1;      k:=time mod c[i,0];      if k=0 then k:=c[i,0];      addedge(cal(c[i,k],time-1),cal(c[i,j],time),h[i]);    end;end;end;beginreadln(n,m,kk);  leftk:=kk;  fillchar(edge,sizeof(edge),0);  fillchar(num,sizeof(num),0);  for i:=0 to 200*(n+2) do first[i]:=-1;  tot:=0;  s:=0;  t:=n+1;  ss:=0;  st:=1;  sum:=2;  num[0]:=2;  for i:=1 to m do begin    read(h[i],c[i,0]);    for j:=1 to c[i][0] do begin      read(c[i,j]);      if c[i,j]=-1 then c[i,j]:=n+1;    end;    readln;  end;  time:=0;  while time<200 do begin    more(time);    flow:=0;    inc(flow,maxflow);    dec(leftk,flow);    if leftk<=0 then begin      writeln(time);      break;    end;    inc(time);  end;if time=200 then writeln('0');end.
      

vijos 1653 疯狂方格取数

   zkw处理负边上跪了很久。网上少有资料

const maxn= 100000;type edgetype=record  toward,cap,cost,next:longint; end;var edge:array[0..maxn] of edgetype; map:array[1..1000,1..1000,0..1] of longint; q,first,slack,d,dist:array[0..maxn] of longint; pd:array[0..maxn] of boolean; i,j,n,m,ss,st,tot,k,x,cnt,point,mincost:longint;function min(x,y:longint):longint;begin if x
      
       -1 do    begin     tmp:=edge[i].toward;     value:=edge[i].cost;     if (edge[i].cap>0) and (d[tmp]>d[j]+value) then      begin       d[tmp]:=d[j]+value;        if not pd[tmp] then         begin          inc(tail);          if tail=maxn then tail:=1;          q[tail]:=tmp;          pd[tmp]:=true;         end;      end;     i:=edge[i].next;    end;   inc(head);   if head=maxn then head:=1;   pd[j]:=false;  end;end;procedure dfs(v:longint);var i,value,tmp:longint;begin pd[v]:=true; i:=first[v]; while i<>-1 do  begin   tmp:=edge[i].toward;   value:=edge[i].cost;   if (edge[i].cap>0) and (not pd[tmp]) and (d[tmp]=d[v]+value) then    begin     dist[tmp]:=dist[v]-value;     dfs(tmp);    end;  i:=edge[i].next;  end;end;function aug(v,flow:longint):longint;var rec,ret,i,tmp,value:longint;begin if v=st then  begin   inc(mincost,flow*(dist[st]-dist[ss]));   exit(flow);  end; rec:=0; i:=first[v]; pd[v]:=true; while i<>-1 do  begin   tmp:=edge[i].toward;   value:=edge[i].cost;   if (not pd[tmp]) and (edge[i].cap>0) then    if dist[v]=dist[tmp]+value then     begin      ret:=aug(tmp,min(flow-rec,edge[i].cap));      dec(edge[i].cap,ret);      inc(edge[i xor 1].cap,ret);      inc(rec,ret);      if rec=flow then exit(flow);     end    else slack[tmp]:=min(slack[tmp],dist[tmp]+value-dist[v]);   i:=edge[i].next;  end; exit(rec);end;function relabel:boolean;var i,delta:longint;begin delta:=maxlongint; for i:= ss to st do if not pd[i] then delta:=min(delta,slack[i]); if delta=maxlongint then exit(false); for i:= ss to st do if pd[i] then inc(dist[i],delta); exit(true);end;procedure init;begin readln(k,m,n); cnt:=m*n; ss:=0; st:=cnt*2+1; tot:=0; point:=0; for i:= ss to st do first[i]:=-1; for i:=1 to n do  for j:= 1 to m do   begin    read(x);    inc(point);map[i,j,0]:=point;    inc(point);map[i,j,1]:=point;    addedge(map[i,j,0],map[i,j,1],1,-x);    addedge(map[i,j,0],map[i,j,1],maxlongint,0);   end; addedge(ss,map[1,1,0],k,0); addedge(map[n,m,1],st,k,0); for i:=1 to n do  for j:= 1 to m do   begin    if i+1<=n then addedge(map[i,j,1],map[i+1,j,0],maxlongint,0);    if j+1<=m then addedge(map[i,j,1],map[i,j+1,0],maxlongint,0);   end;end;procedure costflow;begin spfa; fillchar(pd,sizeof(pd),false); fillchar(dist,sizeof(dist),0); dfs(ss); repeat  for i:= ss to st do slack[i]:=maxlongint;  repeat   fillchar(pd,sizeof(pd),false);  until aug(ss,maxlongint)<=0; until not relabel;end;Begin init; costflow; writeln(mincost);end.
      

vijos 1726 美食节（费用流）

    很明显是一道费用流，如果用常规的方法，把每个厨师每个时刻拆出来的话，由于点太多会爆于是我们考虑了这样一个事实，每个厨师并不需要把他每个时刻的点都扩展出来，一个厨师只有当他做完一个菜是才去考虑让他多做一个菜，这样的话由于一种只有sum(=∑p[i])道菜，所有整个图实际需要的点数就是源点汇点（2个），菜（n个），厨师（m个）以及扩展出来的厨师（sum个，实际只需sum-m，但为了方法我们不妨多几个点）。一开始源点连每道菜连一条容量为菜需求量费用为0的边，汇点和每个厨师连一条容量为1费用为0的边，然后把第i个厨师与第j道菜连一条容量为1费用为厨师做这道菜的时间的边。这样就是一个初始图。跑spfa（由于一次一定是做一道菜，所以就可以省点记录此次增广的流量），然后每次增广后必然会有一个厨师做出了某道菜，这是我们就扫一遍判断是哪个厨师做了菜（开个last数组记录每个厨师当前点与汇点的边，判断哪个厨师的最后一条边容量为0），然后开个chef表示这个厨师至今做了多少道菜。重新增加一个点，这个点与每道菜连一条容量为1费用为（这个厨师做这道菜的时间*这个厨师一共做了多少道菜），然后这个点再与汇点连一条容量为1费用为0的边。开个time计菜，等time=sum时就说明做完了，输出这时的费用就是答案了。

const maxn=300000;type edgetype=record  toward,cap,cost,next:longint; end;var edge:array[0..maxn] of edgetype; minflow,pre,first,q,dist:array[0..maxn] of longint; pd:array[0..maxn] of boolean; p:array[1..40] of longint; data:array[1..40,1..100] of longint; chef:array[1..100] of longint; last:array[1..100] of longint; i,j,s,t,n,m,tot,cnt,time,x:longint;function min(x,y:longint):longint;begin if x
      
       -1 do    begin     tmp:=edge[i].toward;     value:=edge[i].cost;     if (edge[i].cap>0) and (dist[tmp]>dist[j]+value) then      begin       dist[tmp]:=dist[j]+value;       pre[tmp]:=i;       if not pd[tmp] then        begin         inc(tail);         q[tail]:=tmp;         pd[tmp]:=true;        end;      end;     i:=edge[i].next;    end;   inc(head);   pd[j]:=false;  end; if dist[t]=maxlongint then exit(false) else exit(true);end;function mcmf:longint;var u,cost:longint;begin cost:=0; while time
       
        s do    begin     dec(edge[pre[u]].cap);     inc(edge[pre[u] xor 1].cap);     u:=edge[pre[u] xor 1].toward;    end;   inc(cost,dist[t]);   inc(time);   for i:= 1 to m do    if edge[last[i]].cap=0 then     begin      x:=i;      break;     end;   inc(chef[x]);   for i:=1 to n do     addedge(i,n+m+time,1,data[i,x]*chef[x]);   addedge(n+m+time,t,1,0);   last[x]:=tot-2;  end; exit(cost);end;procedure init;begin tot:=0; time:=0; cnt:=0; read(n,m); for i:=1 to n do  begin   read(p[i]);   inc(cnt,p[i]);  end; for i:= 1 to n do  for j:= 1 to m do   read(data[i,j]); s:=n+m+cnt+1;  t:=s+1; for i:= 0 to t do first[i]:=-1; for i:=1 to n do  addedge(s,i,p[i],0); for i:=1 to n do  for j:= 1 to m do   addedge(i,j+n,1,data[i,j]); for i:= 1 to m do chef[i]:=1; for i:=1 to m do  begin   addedge(n+i,t,1,0);   last[i]:=tot-2;  end;end;Begin init; writeln(mcmf);End.
       
      

vijos 1621 终极情报网（费用流）

  网上没有太多题解，因为这本来就是一道很简单的模型，这么简单就不想说了，这道题主要难在两个问题，一个是要保留五位有效数字，一个是关于浮点运算（后面这个东西害得我两节晚自修没了，网上也没大神说一下，第一次遇到浮点运算什么的好讨厌）。前一种我很傻很天真的方法yy然后就完了，但是很难看，下面会给出某蔡大神的空间自行过去研究他的吧。关于第二个问题，这题是求一些实数的运算，可以用两个方法，一个是直接乘，就是把原来的spfa中+号改为*号，那么相应的，建边的时候反向弧的费用就不是-asi而是1/asi，这样就会遇到一个精度问题，所有在增广时必须要把原来的dist[to]<dist[i]*edge[j].cost改为dist[i]*edge[j].cost-dist[to]＞esp（esp=0.000000001）。这样程序才跑得动……第二种方法就是取对数，把*改为+，觉得神奇到不可思议，所以还是由蔡大神的题解来告诉我们这些蒟蒻吧。

type  arr=record    toward,next,cap:longint;    cost:double;  end;var  edge:array[0..1000000]of arr;  dist,minc,a:array[0..100000]of double;  q,first,pre,minf,b:array[0..100000]of longint;  map:array[0..2000,0..2000]of double;  i,j,k,l,s,t,tot,kk,maxflow,n,x:longint;  chose:array[0..10000]of boolean;  spent,h:double;function exp(x:double;y:longint):double;  //快速幂递归版！yy一下就知道为什么用快速幂了begin  if y=1 then exit(x);  exit(exp(x,y div 2)*exp(x,y-(y div 2)));end;function min(x,y:longint):longint;begin  if x>y then exit(y);  exit(x);end;procedure add(i,j,k:longint;l:double);begin  edge[tot].toward:=j;  edge[tot].cap:=k;  edge[tot].cost:=l;  edge[tot].next:=first[i];  first[i]:=tot;  inc(tot);end;procedure addedge(i,j,k:longint;l:double);begin  add(i,j,k,l);  add(j,i,0,1/l);end;function spfa:boolean;var  i,head,tail,flow,j,too:longint;  value,mm:double;begin  fillchar(chose,sizeof(chose),false);  fillchar(dist,sizeof(dist),0);  dist[s]:=1;  head:=1;  tail:=1;  q[1]:=s;  mm:=0.000000001;  chose[s]:=true;  minf[s]:=maxlongint;  while head<=tail do begin    i:=q[head];    j:=first[i];    while j<>-1 do begin      too:=edge[j].toward;      value:=edge[j].cost;      if (edge[j].cap>0) and (dist[i]*value-dist[too]>mm) then begin        dist[too]:=dist[i]*value;        pre[too]:=j;        minf[too]:=min(minf[i],edge[j].cap);        minc[too]:=edge[j].cost;        if not chose[too] then begin          chose[too]:=true;          inc(tail);          q[tail]:=too;        end;      end;      j:=edge[j].next;    end;    inc(head);    chose[i]:=false;  end;  if dist[t]=0 then exit(false);  exit(true);end;procedure mcmf;var  j,k,v:longint;begin  spent:=1;  maxflow:=0;  while spfa do begin    j:=minf[t];    inc(maxflow,j);    v:=t;    while v<>s do begin      spent:=spent*exp(minc[v],j);      k:=pre[v];      dec(edge[k].cap,j);      inc(edge[k xor 1].cap,j);      v:=edge[k xor 1].toward;    end;  end;end;procedure outo;var  ans,i,j,k:longint;begin  {
     writeln(spent);}  spent:=spent*10;  i:=1;  x:=trunc(spent);  while x=0 do begin    spent:=spent*10;    inc(i);    x:=trunc(spent);  end;  spent:=spent/10;  j:=0;  while j<=5 do begin    inc(j);    spent:=spent*10;    b[j]:=trunc(spent);    spent:=spent-b[j];  end;  if b[6]>=5 then inc(b[5]);  k:=5;  while (b[k]>=10) and (k>1) do begin    inc(b[k-1]);    b[k]:=b[k]-10;  end;  if b[1]>9 then    dec(i);  write('0.');  for k:=1 to i-1do    write(0);  for k:=1 to 5 do    write(b[k]);  readln;  readln;  readln;end;begin  readln(n,kk);  fillchar(map,sizeof(map),0);  t:=n+2;  s:=n+1;  tot:=0;  for i:=0 to n+3 do first[i]:=-1;  for i:=1 to n do read(a[i]);  for i:=1 to n do begin    read(b[i]);    if b[i]>0 then      addedge(s,i,b[i],a[i]);  end;  readln;  for i:=1 to n do begin    read(x);    if x>0 then addedge(i,t,maxlongint,1);  end;  readln;  read(j,k);  while (j<>-1) and (k<>-1) do begin    readln(h,l);    addedge(j,k,l,h);    addedge(k,j,l,h);    read(j,k);  end;  addedge(t,t+1,kk,1);  inc(t);  mcmf;  if maxflow

vijos 1525 生命之泉 （费用流）

   这道题和志愿者招募那道题差不多，属于一个类型的，志愿者招募那道题网上可以找个很多好的题解！关于这类题简单的说就是写一些方程，然后会发现一些规律

最核心的就是：

一开始）P[1]=X[1]≥2

 

        P[2]=X[1]+X[2]≥3

 

        P[3]=X[2]+X[3]≥2

可变为）

       P[1]=X[1]-Y[1]=2

 

       P[2]=X[1]+X[2]-Y[2]=3

 

       P[3]=X[2]+X[3]-Y[3]=2    （Y就是一个变量就对了）

然后我们在最前面加一个 P[0]=0的式子，用下一个式子减上一个式子就可以得到

       P[1]-P[0]=X[1]-Y[1]=2

       P[2]-P[1]=X[2]+Y[1]-Y[2]=1

       P[3]-P[2]=-X[1]+X[3]+Y[2]-Y[3]=-1

       P[4]-P[3]=-X[2]-X[3]+Y[3]=-2

将常数项左移，得

       P[1]-P[0]=X[1]-Y[1]-2=0

       P[2]-P[1]=X[2]+Y[1]-Y[2]-1=0

       P[3]-P[2]=-X[1]+X[3]+Y[2]-Y[3]+1=0

       P[4]-P[3]=-X[2]-X[3]+Y[3]+2=0

我们发现一个x或y只会在两个式子里面出现，而且一个是负的，一个是正的！（大神话：很容易联想到网络流）

对于每个x[i]，从-x[i]想+x[i]连一条边（具体要根据题意），对于每个y[i]也是一样，不过y[i]和-y[i]总是出现在一前一后。

这道题比较麻烦……要把最大费用最大流然后转为最小费用最大流跑zkw……

type  arr=record    toward,cap,cost,next:longint;  end;const maxn=1000000;var  edge:array[0..10000]of arr;  first,d,dist,q,slack:array[0..100000]of longint;  chose:array[0..100000]of boolean;  i,j,k,l,s,t,n,m,tot,maxcost,maxflow,kk:longint;procedure add(i,j,k,l:longint);begin  edge[tot].toward:=j;  edge[tot].cap:=k;  edge[tot].cost:=l;  edge[tot].next:=first[i];  first[i]:=tot;  inc(tot);end;procedure addedge(i,j,k,l:longint);begin  add(i,j,k,l);  add(j,i,0,-l);end;function min(x,y:longint):longint;begin  if x>y then exit(y);  exit(x);end;procedure spfa;var  head,tail,i,too,value:longint;begin  fillchar(chose,sizeof(chose),false);  for i:=0 to t do d[i]:=maxlongint;  head:=1;  tail:=1;  q[1]:=s;  chose[s]:=true;  d[s]:=0;  while head<=tail do begin    j:=q[head];    i:=first[j];    while i<>-1 do begin      too:=edge[i].toward;      value:=edge[i].cost;      if (edge[i].cap>0) and (d[too]>d[j]+value) then begin        d[too]:=d[j]+value;        if not chose[too] then begin          inc(tail);          if tail=maxn then tail:=1;          q[tail]:=too;          chose[too]:=true;        end;      end;      i:=edge[i].next;    end;    inc(head);    if head=maxn then head:=1;    chose[j]:=false;  end;end;procedure dfs(v:longint);var  i,value,too:longint;begin  chose[v]:=true;  i:=first[v];  while i<>-1 do begin    too:=edge[i].toward;    value:=edge[i].cost;    if (edge[i].cap>0) and (not chose[too]) and (d[too]=d[v]+value) then begin      dist[too]:=dist[v]-value;      dfs(too);    end;    i:=edge[i].next;  end;end;function aug(v,flow:longint):longint;var  rec,ret,too,value,i:longint;begin  if v=t then begin    inc(maxcost,(dist[t]-dist[s])*flow);    inc(maxflow,flow);    exit(flow);  end;  i:=first[v];  chose[v]:=true;  rec:=0;  while i<>-1 do begin    too:=edge[i].toward;    value:=edge[i].cost;    if (edge[i].cap>0) and (not chose[too]) then      if dist[v]=dist[too]+value then begin        ret:=aug(too,min(flow-rec,edge[i].cap));        dec(edge[i].cap,ret);        inc(edge[i xor 1].cap,ret);        inc(rec,ret);        if rec=flow then exit(flow);      end else        slack[too]:=min(slack[too],dist[too]+value-dist[v]);    i:=edge[i].next;  end;  exit(rec);end;function rel:boolean;var  spent,i:longint;begin  spent:=maxlongint;  for i:=0 to t do    if not chose[i] then spent:=min(spent,slack[i]);  if spent=maxlongint then exit(false);  for i:=0 to t do    if chose[i] then inc(dist[i],spent);  exit(true);end;procedure costflow;begin  spfa;  fillchar(chose,sizeof(chose),false);  fillchar(dist,sizeof(dist),0);  dfs(s);  repeat    for i:=0 to t do slack[i]:=maxlongint;    repeat      fillchar(chose,sizeof(chose),false);    until aug(s,maxlongint)<=0;  until not rel;end;procedure into;begin  readln(n,m,kk);  s:=0;  t:=n+2;  tot:=0;  for i:=0 to t do first[i]:=-1;  addedge(1,t,kk,0);  addedge(s,n+1,kk,0);  for i:=1 to m do begin    readln(j,k,l);    addedge(k+1,j,1,-l);  end;  for i:=1 to n do    addedge(i+1,i,maxlongint,0);  fillchar(d,sizeof(d),0);end;begin  into;  costflow;  writeln(maxcost);  readln;  readln;end.

vijos 1499 炸毁燃料库

   建边一直跪……为了容易想容易看，结果竟然就跪了……

   后来认真想了好久（Orz蔡大神的代码）才终于过了……线性规划

一开始

   x[1]+x[2]+x[3]+...+x[m]   <=k;

   x[2]+x[3]+x[4]+...+x[m+1] <=k;

   x[3]+x[4]+x[5]+...+x[m+2] <=k;

   ......

   x[n-m+1]+...+x[n]         <=k;

转换为

                                   0=0

   x[1]+x[2]+x[3]+...+x[m]   -y[1]-k=0;

   x[2]+x[3]+x[4]+...+x[m+1] -y[2]-k=0;

   x[3]+x[4]+x[5]+...+x[m+2] -y[3]-k=0;

   ...

   x[n-m+1]+...+x[n] -y[n-m+1]-k=0;

下面减上面

  

1   x[1]+x[2]+x[3]+...+x[m]  -y[1]-k=0

2   x[m+1]  -x[1]          +y[1]-y[2] =0;

3   x[m+2]  -x[2]          +y[2]-y[3] =0;

4   x[m+3]  -x[3]          +y[3]-y[4] =0;

   ......

（    x[m+m]  -x[m]          +y[m]-y[m+1]=0

    x[m+m+1]-x[m+1]             ）

   ......

n-m+1   x[n]    -x[n-m]        +y[n-m]-y[n-m+1]=0;

n-m+2  -x[n-m+1]-x[n-m]...-x[n]+y[n-m+1]+k=0

然后就是中间那种情况会导致图有两种结果，判断条件是m≥n-m 是的话就是第一种图（没有括号那种情况），不是的话就是（有括号的图）

 

type  arr=record    toward,next,cap,cost:longint;  end;const  mm=1000000;var  edge:array[0..100000]of arr;  first,dist,d,q,slack,a:array[0..mm]of longint;  i,j,k,l,n,m,s,t,tot,maxcost,maxflow,kk:longint;  chose:array[0..mm]of boolean;procedure add(i,j,k,l:longint);begin  edge[tot].toward:=j;  edge[tot].cap:=k;  edge[tot].cost:=l;  edge[tot].next:=first[i];  first[i]:=tot;  inc(tot);end;procedure addedge(i,j,k,l:longint);begin  add(i,j,k,l);  add(j,i,0,-l);end;function min(x,y:longint):longint;begin  if x>y then exit(y);  exit(x);end;procedure spfa;var  head,tail,i,too,value:longint;begin  fillchar(chose,sizeof(chose),false);  for i:=0 to t do d[i]:=maxlongint;  head:=1;  tail:=1;  q[1]:=s;  chose[s]:=true;  d[s]:=0;  while head<=tail do begin    j:=q[head];    i:=first[j];    while i<>-1 do begin      too:=edge[i].toward;      value:=edge[i].cost;      if (edge[i].cap>0) and (d[too]>d[j]+value) then begin        d[too]:=d[j]+value;        if not chose[too] then begin          inc(tail);          if tail=mm then tail:=1;          q[tail]:=too;          chose[too]:=true;        end;      end;      i:=edge[i].next;    end;    inc(head);    if head=mm then head:=1;    chose[j]:=false;  end;end;procedure dfs(v:longint);var  i,value,too:longint;begin  chose[v]:=true;  i:=first[v];  while i<>-1 do begin    too:=edge[i].toward;    value:=edge[i].cost;    if (edge[i].cap>0)  and (d[too]=d[v]+value) then begin      dist[too]:=dist[v]-value;      dfs(too);    end;    i:=edge[i].next;  end;end;function aug(v,flow:longint):longint;var  rec,ret,i,too,value:longint;begin  if v=t then begin    inc(maxcost,(dist[t]-dist[s])*flow);    inc(maxflow,flow);    exit(flow);  end;  rec:=0;  chose[v]:=true;  i:=first[v];  while i<>-1 do begin    too:=edge[i].toward;    value:=edge[i].cost;    if (edge[i].cap>0) and (not chose[too]) then      if dist[v]=dist[too]+value then begin        ret:=aug(too,min(flow-rec,edge[i].cap));        dec(edge[i].cap,ret);        inc(edge[i xor 1].cap,ret);        inc(rec,ret);        if rec=flow then exit(flow);      end else        slack[too]:=min(slack[too],dist[too]+value-dist[v]);    i:=edge[i].next;  end;  exit(rec);end;function rel:boolean;var  spent,i:longint;begin  spent:=maxlongint;  for i:=0 to t do    if not chose[i] then spent:=min(spent,slack[i]);  if spent=maxlongint then exit(false);  for i:=0 to t do    if chose[i] then inc(dist[i],spent);  exit(true);end;procedure maxc;begin  spfa;  fillchar(chose,sizeof(chose),false);  fillchar(dist,sizeof(dist),0);  dfs(s);  repeat    for i:=0 to t do slack[i]:=maxlongint;    repeat      fillchar(chose,sizeof(chose),false);    until aug(s,maxlongint)<=0;  until not rel;end;procedure into;begin  readln(n,m,kk);  s:=0;  t:=n-m+3;  for i:=0 to t do first[i]:=-1;  tot:=0;  for i:=1 to n do    read(a[i]);  addedge(s,n-m+2,kk,0);  addedge(1,t,kk,0);  if m>=n-m then begin    for i:=1 to n-m do      addedge(i+1,1,1,-a[i]);    for i:=n-m+1 to m do      addedge(n-m+2,1,1,-a[i]);    for i:=m+1 to n do      addedge(n-m+2,i-m+1,1,-a[i]);  end else begin    for i:=1 to m do      addedge(i+1,1,1,-a[i]);    for i:=m+1 to n-m do      addedge(i+1,i-m+1,1,-a[i]);    for i:=n-m+1 to n do      addedge(n-m+2,i-m+1,1,-a[i]);  end;  for i:=1 to n-m+1 do    addedge(i+1,i,maxlongint,0);  fillchar(d,sizeof(d),0);end;begin  into;  maxc;  writeln(maxcost);end.

vijos 1734 海拔 （网络流转为最短路）

   orz这题特别神奇，作为蒟蒻完全被考倒了。

   找了网上的题解最好的就是这个了 （其实有另一个……但是莫名挂了，orz）。

   这题很容易想到一个最小割模型，但是会tle！所以只能转为对偶图，这个神奇的东西推荐去看集训队论文：周冬《两极相通——浅析最大—最小定理在信息学竞赛中的应用》。讲的很详细！

   然后就是spfa，裸的spfa不能过，所以要加lll+slt优化！

   或者是二叉堆优化的dij……

   然后这题由于信息量太大就跪了很久……先搞懂一系列概念，然后就是略蛋疼的spfa了，在tle无数次后终于把spfa改的能过最后一个点（一直卡最后一个点orz）……

//spfa版  type  arr=record    toward,next,cost:longint;  end;const  mm=300000;var  edge:array[0..5*mm]of arr;  first,d,q:array[0..mm]of longint;  map:array[0..2000,0..2000]of longint;  f:array[0..mm]of boolean;  i,j,k,l,n,m,tot,s,t,sum:longint;procedure addedge(i,j,k:longint);begin  inc(tot);  edge[tot].toward:=j;  edge[tot].next:=first[i];  first[i]:=tot;  edge[tot].cost:=k;end;procedure spfa(v:longint);var  head,tail,i,too,j,value,len,k:longint;  sum:int64;begin  sum:=0;  len:=1;  fillchar(f,sizeof(f),false);  fillchar(d,sizeof(d),$7f);  d[v]:=0;  head:=0;  tail:=1;  q[1]:=v;  f[v]:=true;  while head<>tail do begin    inc(head);    if head>mm then head:=1;    while d[q[head]]>sum div len do begin  //lll优化，记得sum要int64！因为这个跪了一节晚自修！      inc(tail);      if tail>mm then tail:=1;      q[tail]:=q[head];      inc(head);      if head>mm then head:=1;    end;    j:=q[head];    i:=first[j];    dec(len);    dec(sum,d[j]);    while i<>-1 do begin      value:=edge[i].cost;      too:=edge[i].toward;      if (d[j]+value
      
       mm then k:=1;          if d[too]
       
        mm then tail:=1;            q[tail]:=too;          end;        end;      end;      i:=edge[i].next;    end;    f[j]:=false;  end;end;procedure into;begin  s:=0;  t:=n*n+1;  sum:=0;  tot:=0;  for i:=0 to n do    map[0,i]:=t;  for i:=0 to n do    map[i,n+1]:=t;  for i:=0 to n do    map[i,0]:=s;  for i:=0 to n do    map[n+1,i]:=s;  for i:=1 to n do    for j:=1 to n do begin      inc(sum);      map[i,j]:=sum;    end;  for i:=1 to n+1 do    for j:=1 to n do begin      read(k);      addedge(map[i,j],map[i-1,j],k);    end;  for i:=1 to n do    for j:=1 to n+1 do begin      read(k);      addedge(map[i,j-1],map[i,j],k);    end;  for i:=1 to n+1 do    for j:=1 to n do begin      read(k);      addedge(map[i-1,j],map[i,j],k);    end;  for i:=1 to n do    for j:=1 to n+1 do begin      read(k);      addedge(map[i,j],map[i,j-1],k);    end;end;procedure outo;begin  readln(n);  for i:=0 to n*n+2 do first[i]:=-1;end;begin  outo;  into;  spfa(s);  writeln(d[t]);end.//据说这题dij快，然后就写了下，果然快了很多&……type  arr=record    toward,next,cost:longint;  end;  ar=record    value,toward:longint;  end;const  mm=300000;var  edge:array[0..5*mm]of arr;  first,g:array[0..mm]of longint;  head:array[0..5*mm]of ar;  map:array[0..2000,0..2000]of longint;  f:array[0..mm]of boolean;  i,j,k,l,n,m,tot,s,t,sum,len:longint;procedure addedge(i,j,k:longint);begin  inc(tot);  edge[tot].toward:=j;  edge[tot].next:=g[i];  g[i]:=tot;  edge[tot].cost:=k;end;procedure into;begin    readln(n);  for i:=0 to n*n+2 do g[i]:=-1;  s:=n*n+1;  t:=n*n+2;  sum:=0;  tot:=0;  for i:=0 to n do    map[0,i]:=t;  for i:=0 to n do    map[i,n+1]:=t;  for i:=0 to n do    map[i,0]:=s;  for i:=0 to n do    map[n+1,i]:=s;  for i:=1 to n do    for j:=1 to n do begin      inc(sum);      map[i,j]:=sum;    end;  for i:=1 to n+1 do    for j:=1 to n do begin      read(k);      addedge(map[i,j],map[i-1,j],k);    end;  for i:=1 to n do    for j:=1 to n+1 do begin      read(k);      addedge(map[i,j-1],map[i,j],k);    end;  for i:=1 to n+1 do    for j:=1 to n do begin      read(k);      addedge(map[i-1,j],map[i,j],k);    end;  for i:=1 to n do    for j:=1 to n+1 do begin      read(k);      addedge(map[i,j],map[i,j-1],k);    end;end;procedure swap(a,b:longint);var  j:ar;begin  j:=head[a];  head[a]:=head[b];  head[b]:=j;  first[head[a].toward]:=a;  first[head[b].toward]:=b;end;procedure decre(i:longint);begin  while (i<>1) and (head[i].value
        
         0 do begin    i:=head[1].toward;    if i=t then exit;    swap(1,len);    dec(len);    headpify;    j:=g[i];    while j<>-1 do begin      too:=edge[j].toward;      va:=edge[j].cost;      if first[too]<=len then relax(i,too,va);      j:=edge[j].next;    end;  end;end;begin  into;  dij;  writeln(head[1].value);end.