BZOJ1927 Starrace

{$INLINE ON}
program bzoj1927;
 
type tnode=record
        n,c,w,next:longint;
     end;
 
const maxn=2017;
      maxm=1000017;
      maxint=longint($3f3f3f3f);
      e9=1000000000;
 
var g,q,dis,dlt,arc,pre,a:array[0..maxn] of longint;
    v:array[0..maxn] of boolean;
    mem:array[0..maxm] of tnode;
    barc:array[0..maxn,0..maxn] of boolean;
    n,m,memsize,st,trm,frt,rer,cost,flow,sa:longint;
 
function min(i,j:longint):longint; inline; begin
if i<j then exit(i) else exit(j);  end;
function max(i,j:longint):longint; inline; begin
if i>j then exit(i) else exit(j);  end;
 
procedure insnbs(u,v,ic,iw:longint);
begin
inc(memsize); with mem[memsize] do begin
        n:=v; c:=ic; w:=iw; next:=g[u];
end; g[u]:=memsize;
inc(memsize); with mem[memsize] do begin
        n:=u; c:=0; w:=-iw; next:=g[v];
end; g[v]:=memsize;
end;
 
procedure ek_spfa;
var head,tail,u,w,t1:longint;
begin
cost:=0; flow:=0; dis[trm]:=0; while dis[trm]<maxint do begin
        fillchar(dis,sizeof(dis),$3f); frt:=0; rer:=1; q[1]:=st; v[st]:=true; dis[st]:=0; dlt[st]:=maxint; pre[st]:=0;
        while frt<>rer do begin frt:=frt mod maxn+1; head:=q[frt];
                t1:=g[head]; while t1<>0 do begin tail:=mem[t1].n;
                        if (dis[tail]>dis[head]+mem[t1].w)and(mem[t1].c>0) then begin
                                dis[tail]:=dis[head]+mem[t1].w;
                                pre[tail]:=head;
                                arc[tail]:=t1;
                                dlt[tail]:=min(dlt[head],mem[t1].c);
                                if not v[tail] then begin rer:=rer mod maxn+1; q[rer]:=tail; v[tail]:=true; end;
                        end; t1:=mem[t1].next;
                end; v[head]:=false;
        end; if dis[trm]<maxint then begin
                inc(flow,dlt[trm]); inc(cost,dlt[trm]*dis[trm]); u:=trm; w:=dlt[trm];
                while u<>st do begin dec(mem[arc[u]].c,w); inc(mem[arc[u]xor 1].c,w); u:=pre[u]; end;
        end;
end;
end;
 
procedure init;
var i,j,k,u,v,w:longint;
begin
fillchar(g,sizeof(g),0); memsize:=1; readln(n,m); st:=n<<1+1; trm:=st+1;
for i:=1 to n do begin read(a[i]); inc(sa,a[i]); insnbs(st,i,1,0); insnbs(i+n,trm,1,0); insnbs(i,trm,1,0); end;
for i:=1 to m do begin readln(u,v,w); if u>v then begin k:=u; u:=v; v:=k; end;
        if w<a[v] then insnbs(u,n+v,1,w-a[v]);
end; n:=n<<1+2;
end;
 
begin
init;
ek_spfa;
writeln(sa+cost);
end.