记录编号	69557	评测结果	AAAAAAAAAA
题目名称	[NOI 2008]志愿者招募	最终得分	100
用户昵称	GDFRWMY	是否通过	通过
代码语言	Pascal	运行时间	1.319 s
提交时间	2013-09-18 13:01:04	内存使用	3.99 MiB

const


  maxn=1005;

  maxq=1000005;

  maxinf=maxlongint div 2;

type

  node=^node2;

  node2=record

    y,c,w:longint;

    next,back:node;

  end;

var

  n,m,s,t,ans:longint;

  q:array[0..maxq] of longint;

  v:array[0..maxn] of boolean;

  pre,d:array[0..maxn] of longint;

  ls,fa:array[0..maxn] of node;



procedure add(x,y,flow,cost:longint);

  var

    p:node;

  begin

    new(p); p^.y:=y; p^.c:=flow; p^.w:=cost; p^.next:=ls[x]; ls[x]:=p;

    new(p); p^.y:=x; p^.c:=0;    p^.w:=-cost;p^.next:=ls[y]; ls[y]:=p;

    ls[x]^.back:=ls[y];

    ls[y]^.back:=ls[x];

  end;



procedure init;

  var

    i,st,ed,w,pre,now:longint;

  begin

    readln(n,m);

    pre:=0;

    s:=0; t:=n+2;

    for i:=s to t do ls[i]:=nil;

    for i:=1 to n+1 do

    begin

      if i=n+1 then w:=0 else read(w);

      now:=pre-w;

      if now<0 then add(i,t,-now,0)

        else add(s,i,now,0);

      pre:=w;

    end;

    readln;

    for i:=1 to m do

    begin

      readln(st,ed,w);

      add(ed+1,st,maxinf,w);

    end;

    for i:=1 to n do add(i,i+1,maxinf,0);

  end;



function spfa:boolean;

  var

    i,head,tail,now:longint;

    p:node;

  begin

    for i:=s to t do

    begin

      d[i]:=maxinf;

      v[i]:=false;

    end;

    d[s]:=0;

    v[s]:=true;

    head:=0; tail:=1; q[1]:=s;

    repeat

      head:=(head+1) mod maxq;

      now:=q[head];

      p:=ls[now];

      v[now]:=false;

      while p<>nil do

      begin

        if (p^.c>0) and (d[p^.y]>d[now]+p^.w) then

        begin

          d[p^.y]:=d[now]+p^.w;

          pre[p^.y]:=now;

          fa[p^.y]:=p;

          if not v[p^.y] then

          begin

            v[p^.y]:=true;

            tail:=(tail+1) mod maxq;

            q[tail]:=p^.y;

          end;

        end;

        p:=p^.next;

      end;

    until head>=tail;

    if d[t]=maxinf then exit(false) else exit(true);

  end;



procedure change;

  var

    i,min:longint;

  begin

    min:=maxinf;

    i:=t;

    repeat

      if fa[i]^.c<min then min:=fa[i]^.c;

      i:=pre[i];

    until i=s;

    i:=t;

    repeat

      dec(fa[i]^.c,min);

      inc(fa[i]^.back^.c,min);

      i:=pre[i];

    until i=s;

    ans:=ans+d[t]*min;

  end;



procedure main;

  begin

    ans:=0;

    while spfa do change;

    writeln(ans);

  end;



begin

  assign(input,'employee.in'); reset(input);

  assign(output,'employee.out');rewrite(output);

  init;

  main;

  close(input);      close(output);

end.