nbu 2429 Transfer stations(三)
edg[m].to=u,edg[m].flow=vf,edg[m].next=g[v],g[v]=m++;
}
bool bfs(int s,int t){
clr(gap,0,n),clr(dis,-1,n);
gap[dis[t]=0]++,dis[s]=-1;
for(q[head=tail=0]=t;head<=tail;){
int u=q[head++];
for(int i=g[u];i!=-1;i=edg[i].next){
edge& e=edg[i],ee=edg[i^1];
if(dis[e.to]==-1 && ee.flow>0){
gap[dis[e.to]=dis[u]+1]++;
q[++tail]=e.to;
}
}
}
return dis[s]!=-1;
}
type maxFlow(int s,int t){
if(!bfs(s,t)) return 0;
type res=0,a;
int i;
for(i=0;i
pre[s]=s,cur[s]=g[s],cur[t]=g[t];
for(int u=s;dis[s]
if(u==t){
for(a=-1;u!=s;u=pre[u])
getmin(a,edg[cur[pre[u]]].flow);
for(u=t;u!=s;u=pre[u]){
edg[cur[pre[u]]].flow-=a;
edg[cur[pre[u]]^1].flow+=a;
}
res+=a;
}
bool ok=0;
for(i=cur[u];i!=-1;i=edg[i].next){
edge& e=edg[i];
if(dis[u]==dis[e.to]+1 && e.flow>0){
cur[u]=i,pre[e.to]=u,u=e.to;
ok=1;break;
}
}
if(ok) continue;
int mindis=n-1;
for(i=g[u];i!=-1;i=edg[i].next){
edge& e=edg[i];
if(mindis>dis[e.to] && e.flow>0)
mindis=dis[e.to],cur[u]=i;
}
if(--gap[dis[u]]==0) break;
gap[dis[u]=mindis+1]++,u=pre[u];
}
return res;
}
}p;
void run(){
int i,j;
p.init(n+1);
int tot=0;
for(i=1;i<=n;i++)
scanf("%d",&pr[i]);
clr(d,0,n);
for(U=0,i=1;i<=m;i++){
scanf("%d%d%d",&a[i],&b[i],&c[i]);
U+=c[i],d[a[i]]+=c[i],d[b[i]]+=c[i];
p.insert(a[i],b[i],c[i],c[i]);
}
for(i=1;i<=n;i++){
p.insert(0,i,U);
p.insert(i,n+1,U+2*pr[i]-d[i]);
} www.2cto.com
printf("%d\n",(U*n-p.maxFlow(0,n+1))/2);
}
void preSof(){
}
int main(){
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
preSof();
//run();
while(~scanf("%d%d",&n,&m)) run();
//for(scanf("%d",&TS);cas<=TS;cas++) run();
return 0;
}