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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
| program bzoj_3931;
const inf=maxlongint<<16;
var d:array[1..2,1..500]of longint;
l,ll:array[1..200000]of record ed,pre:longint; f:int64; end;
n,m,i,tot,a,b,c,k,ss,tt:longint;
lst,st:array[1..1000]of longint;
function min(a,b:int64):int64;
begin
if a<b then exit(a) else exit(b);
end;
procedure link(a,b:longint;d:int64);
begin
inc(tot);
ll[tot].pre:=lst[a];
lst[a]:=tot;
ll[tot].ed:=b;
ll[tot].f:=d;
end;
procedure insert(a,b:longint;f:int64);
begin
inc(tot);
l[tot].pre:=st[a];
st[a]:=tot;
l[tot].ed:=b;
l[tot].f:=f;
inc(tot);
l[tot].pre:=st[b];
st[b]:=tot;
l[tot].ed:=a;
l[tot].f:=0;
end;
procedure spfa(t,st:longint);
const qs=500;
var q:array[1..qs]of longint;
v:array[1..qs]of boolean;
hd,tl,k:longint;
begin
hd:=0;
tl:=1;
d[t,st]:=0;
q[1]:=st;
fillchar(v,sizeof(v),false);
v[st]:=true;
while hd<>tl do
begin
inc(hd);
if hd>qs then hd:=1;
k:=lst[q[hd]];
while k<>0 do
begin
if d[t,q[hd]]+ll[k].f<d[t,ll[k].ed] then
begin
d[t,ll[k].ed]:=d[t,q[hd]]+ll[k].f;
if not v[ll[k].ed] then
begin
v[ll[k].ed]:=true;
inc(tl);
if tl>qs then tl:=1;
q[tl]:=ll[k].ed;
end;
end;
k:=ll[k].pre;
end;
v[q[hd]]:=false;
end;
end;
procedure push_flow;
const qs=10000;
var h,e:array[1..1000]of int64;
q:array[1..qs]of longint;
hd,tl,k:longint;
maxf,f:int64;
begin
fillchar(h,sizeof(h),0);
fillchar(e,sizeof(e),0);
fillchar(q,sizeof(q),0);
maxf:=0;
e[ss]:=inf;
e[tt]:=-inf;
h[ss]:=tt;
hd:=0;
tl:=1;
q[1]:=ss;
while hd<>tl do
begin
inc(hd);
if hd>qs then hd:=1;
k:=st[q[hd]];
while k<>0 do
begin
while (e[q[hd]]>0)and(l[k].f>0)and((q[hd]=ss)or(h[q[hd]]=h[l[k].ed]+1)) do
begin
f:=min(e[q[hd]],l[k].f);
dec(e[q[hd]],f);
inc(e[l[k].ed],f);
dec(l[k].f,f);
inc(l[k xor 1].f,f);
if l[k].ed=tt then inc(maxf,f);
if (l[k].ed<>ss)and(l[k].ed<>tt) then
begin
inc(tl);
if tl>qs then tl:=1;
q[tl]:=l[k].ed;
end;
end;
k:=l[k].pre;
end;
if (e[q[hd]]>0)and(q[hd]<>ss)and(q[hd]<>tt) then
begin
inc(h[q[hd]]);
inc(tl);
if tl>qs then tl:=1;
q[tl]:=q[hd];
end;
end;
writeln(maxf);
end;
begin
readln(n,m);
tot:=0;
for i:=1 to m do
begin
readln(a,b,c);
link(a,b,c);
link(b,a,c);
end;
fillchar(d,sizeof(d),$3f);
spfa(1,1);
spfa(2,n);
tot:=1;
for i:=1 to n do
begin
k:=lst[i];
while k<>0 do
begin
if d[1,i]+ll[k].f+d[2,ll[k].ed]=d[1,n] then insert(i<<1,ll[k].ed<<1-1,inf>>8);
k:=ll[k].pre;
end;
end;
for i:=1 to n do
begin
readln(c);
if (i<>1)and(i<>n) then insert(i<<1-1,i<<1,c);
end;
ss:=2;
tt:=n<<1-1;
push_flow;
end.
|