BZOJ 3931

传送门

先一正一反两遍最短路

然后对于某条边,若$1$到它的一个端点的距离与它的另一个端点到$n$的距离之和再加上这条边的长度等于$1$到$n$的长度的话,(也就是说$dis_{1,a}+dis_{b,n}+dis_{a,b}=dis_{1,n}$),说明这条边属于最短路图

这样搞出最短路图,然后拆点裸上最大流就是答案

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.