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
70
71
72
73
74
75
76
77
78
79
80
| #include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
const int inf = 0x3f3f3f3f;
int cnt = 1;
int n,m,s,t;
int head[N];
struct edge {
int u, v, c, val, nxt;
edge(int u = 0, int v = 0, int c = 0, int val = 0, int nxt = 0): u(u), v(v), c(c), val(val), nxt(nxt) {}
}e[N*10];
void ADD(int u,int v,int c){
cnt++;
e[cnt]=edge(u,v,c,0,head[u]);
head[u]=cnt;
}
void add_edge(int u,int v,int c){
ADD(u,v,c);
ADD(v,u,0);
}
int now[N],dep[N];
bool bfs(){
memcpy(now,head,sizeof head);
memset(dep,0,sizeof dep);
queue<int>q;
dep[s]=1;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
int c=e[i].c;
if(!c||dep[v]!=0) continue;
dep[v]=dep[u]+1;
q.push(v);
}
}
return dep[t]!=0;
}
int dfs(int u,int t,int flow){
if(u==t) return flow;
int nowflow=0;
for(int i=now[u];i&&flow>nowflow;i=e[i].nxt){
now[u]=i;
int v=e[i].v;
int c=e[i].c;
if(!c||dep[v]!=dep[u]+1) continue;
int ff=dfs(v,t,min(c,flow-nowflow));
if(ff) nowflow+=ff,e[i].c-=ff,e[i^1].c+=ff;
else dep[v]=inf;
}
return nowflow;
}
int maxflow(){
int ans=0;
while(bfs()){
int nowflow;
while((nowflow=dfs(s,t,inf))) ans+=nowflow;
}
return ans;
}
int main() {
cin>>n>>m;
s=n+1,t=s+1;
int sum=0;
for(int i=1;i<=n;i++){
int aa;
cin>>aa;
if(aa>0) add_edge(s,i,aa),sum+=aa;
else add_edge(i,t,-aa);
}
for(int i=1;i<=m;i++){
int aa,bb,val;
cin>>aa>>bb>>val;
add_edge(aa,bb,val);
}
cout<<sum-maxflow();
}
|