Www Nudeactressworld R 67 220 93 13 A %5BCOAT%20KURATATSU%5DB S R%A5%D0%A5%B5%A5%E9%20BOX%20%C6%C5%C9%B3%C2%DE%D2%F9%C5%B0%95%B7%BEt%81%BB 1 En 1 Nude Actress World 【NOI2008】 志愿者招募 - datam - 博客园

 1 (*
 2  *Problem: NOI2008 自愿者招募
 3  *Author : Chen Yang
 4  *Time  : 2012.5.18
 5  *State : AC
 6  *Memo : 网络流
 7 *)
 8 program employee;
 9 uses math;
 10 const max=100000000;
 11  maxn=2020;
 12 type
 13  ty1=^ty2;
 14  ty2=record
 15  x,f,v,fa:longint;
 16  next,up:ty1;
 17  end;
 18 
 19 var
 20  n,m,s,t,flow,tot,ans:longint;
 21  first,fa:array[0..maxn] of ty1;
 22  dui,dis,mflow:array[0..maxn] of longint;
 23  get:array[0..maxn] of boolean;
 24 //==================
 25 procedure insert(x,y,f,v:longint);  inline;
 26 var
 27  p,q:ty1;
 28 begin
 29  new(p);
 30  p^.x:=y; p^.f:=f; p^.v:=v; p^.fa:=x;
 31  p^.next:=first[x]; first[x]:=p;
 32  new(q);
 33  q^.x:=x; q^.f:=0; q^.v:=-v; q^.fa:=y;
 34  q^.next:=first[y]; first[y]:=q;
 35  p^.up:=q; q^.up:=p;
 36 end;
 37 //==================
 38 procedure built;
 39 var
 40  i,x,y,z:longint;
 41 begin
 42  read(n,m);
 43  s:=0; t:=n+2; y:=0;
 44  for i:=1 to n do
 45  begin
 46  read(x);
 47 if x-y>0 then begin insert(s,i,x-y,0); inc(tot,x-y); end
 48 else if x-y<0 then insert(i,t,y-x,0);
 49 y:=x;
 50 insert(i+1,i,max,0);
 51  end;
 52  insert(n+1,t,x,0);
 53  for i:=1 to m do
 54  begin
 55  read(x,y,z);
 56 insert(x,y+1,max,z);
 57  end;
 58 end;
 59 //==================
 60 procedure spfa;
 61 var
 62  l,r,x:longint;
 63  p:ty1;
 64 begin
 65  fillchar(get,sizeof(get),false);
 66  fillchar(dis,sizeof(dis),$7);
 67  fillchar(mflow,sizeof(mflow),$7);
 68  l:=0; r:=1; dui[1]:=s; dis[s]:=0;
 69  while l<>r do
 70  begin
 71 inc(l); if l>maxn then l:=0;
 72 x:=dui[l]; get[x]:=false;
 73 p:=first[x];
 74 while p<>nil do
 75 begin
 76  if (p^.f>0) and (dis[p^.x]>dis[x]+p^.v) then
 77  begin
 78 dis[p^.x]:=dis[x]+p^.v; mflow[p^.x]:=min(mflow[x],p^.f);
 79 fa[p^.x]:=p;
 80 if not get[p^.x] then
 81 begin
 82 get[p^.x]:=true;
 83 inc(r); if r>maxn then r:=0;
 84 dui[r]:=p^.x;
 85 end;
 86  end;
 87  p:=p^.next;
 88 end;
 89  end;
 90  inc(flow,mflow[t]); inc(ans,mflow[t]*dis[t]);
 91  p:=fa[t];
 92  while p<>nil do
 93  begin
 94  dec(p^.f,mflow[t]);
 95  inc(p^.up^.f,mflow[t]);
 96 p:=fa[p^.fa];
 97  end;
 98 end;
 99 //==================
100 begin
101  assign(input,'employee.in'); reset(input);
102  assign(output,'employee.out'); rewrite(output);
103  built;
104  while flow<tot do spfa;
105  writeln(ans);
106  close(input); close(output);
107 end.