1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
| #include<bits/stdc++.h> #define REG register using namespace std; inline void read(int& x){ REG char c; while(!isdigit(c=getchar()));x=c^48; while(isdigit(c=getchar()))x=(x*10)+(c^48); } typedef long long ll; const int N=5005,M=100005; const ll INF=0x3f3f3f3f3f3f3f3fll;
int n,m,s,t,u,v;
int Nv[N],Mv[M];
struct Edge{int v,nxt,w;}ed[M]; int head[N],cur[N],cnt=1; inline void adde(int u,int v,int w){ed[++cnt]=(Edge){v,head[u],w},head[u]=cnt;} inline void add(int u,int v,int w){adde(u,v,w),adde(v,u,0);}
ll Mf;
int dep[N];
queue<int> Q;
bool bfs(){ memset(dep,0,sizeof dep); while(Q.size()) Q.pop(); Q.push(s),dep[s]=1,cur[s]=head[s]; while(Q.size()){ int now=Q.front();Q.pop(); for(REG int i=head[now];i;i=ed[i].nxt){ int v=ed[i].v,w=ed[i].w; if((!w)||dep[v]) continue; dep[v]=dep[now]+1,Q.push(v),cur[v]=head[v]; if(v==t) return 1; } } return 0; }
ll dfs(int now,ll flow){ if(now==t) return flow; ll rst=flow; for(REG int i=cur[now];i&&rst;i=ed[i].nxt){ int v=ed[i].v; if(dep[v]!=dep[now]+1||!ed[i].w) continue; cur[now]=i; ll k=dfs(v,min(1ll*ed[i].w,rst)); if(!k) dep[v]=0; ed[i].w-=k,ed[i^1].w+=k,rst-=k; } return flow-rst; }
ll ans;
inline void Work(){ read(n),read(m),s=n+m+1,t=s+1; for(REG int i=1;i<=n;++i) read(Nv[i]),add(i,t,Nv[i]); for(REG int i=1;i<=m;++i) read(u),read(v),read(Mv[i]),add(n+i,u,INF),add(n+i,v,INF),add(s,n+i,Mv[i]),ans+=Mv[i]; while(bfs()) if(Mf=dfs(s,INF)) ans-=Mf; printf("%lld\n",ans); }
int main(){Work();}
|