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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
| #include<cstdio>
#include<cstring>
using namespace std;
const int inf=1e9;
const int N=3e6;
struct edge
{
int from,to,next,cap,flow;
}e[N];
int cnt,n,m,r,sour,sink,head[N],l[N],ans,q[N],p[N],tot;
inline int min(int i,int j)
{
return i<j?i:j;
}
int dfs(int x,int now)
{
if(x==sink||!now)
return now;
int t=now,detla;
for(int i=head[x];i;i=e[i].next)
{
if(e[i].cap>e[i].flow&&l[e[i].to]==l[x]+1)
{
detla=dfs(e[i].to,min(t,e[i].cap-e[i].flow));
if(!detla)
l[e[i].to]=0;
e[i].flow+=detla;
e[((i-1)^1)+1].flow-=detla;
t-=detla;
if(t==0)
break;
}
}
return now-t;
}
inline void add(int u,int v,int l)
{
e[++cnt]=(edge){u,v,head[u],l,0};
head[u]=cnt;
e[++cnt]=(edge){v,u,head[v],0,0};
head[v]=cnt;
}
inline bool find()
{
memset(l,0,sizeof(l));
int h=1,t=1;
q[1]=sour;
l[sour]=1;
while(h<=t)
{
int x=q[h++];
for(int i=head[x];i;i=e[i].next)
if(!l[e[i].to]&&e[i].cap>e[i].flow)
{
q[++t]=e[i].to;
l[e[i].to]=l[x]+1;
if(e[i].to==sink)
return true;
}
}
return false;
}
inline void dinic()
{
while(find())
ans+=dfs(sour,inf);
}
inline void read(int &x)
{
char ch;
int f=1;
x=0;
do
{
if(ch=='-')
f=-1;
ch=getchar();
}while(!('0'<=ch&&ch<='9'));
do
{
x=(x<<3)+(x<<1)+ch-48;
ch=getchar();
}while('0'<=ch&&ch<='9');
x*=f;
}
int main()
{
int _;
read(_);
++_;
while(--_)
{
cnt=0;
ans=0;
tot=0;
memset(e,0,sizeof(e));
memset(head,0,sizeof(head));
read(n);
read(m);
sour=0;
sink=n+m+1;
for(int i=1;i<=n;i++)
{
int r;
read(r);
add(i+m,sink,r);
}
for(int i=1;i<=m;i++)
{
int a,b,c;
read(a);
read(b);
read(c);
add(i,a+m,inf);
add(i,b+m,inf);
add(sour,i,c);
tot+=c;
}
dinic();
printf("%d\n",tot-ans);
}
return 0;
}
|