BZOJ 4006

传送门

注意到题上的$p\leq 10$,所以可以把所有情报站间的连通状态压到一个longint里表示

设$d_{i,j}$为包含$i$点的斯坦纳树,连通状态为$j$时的最小代价,$d_{i,j}=min\lbrace d_{i,k}+d_{i,j-k}\rbrace(k是j的子状态,所以j-k也是j的子状态)$

若$i$是情报站且$j$仅包含$i$一个点的状态则$d_{i,j}=0$

转移方程$d_{i,j}=min(d_{i,j},d_{i’,j}+dis_{i,i’})$可以直接拿SPFA来转移

最后再把这些状态合并一下就行了

Tips:枚举一个状态的所有子状态时的那个位运算的姿势比较神奇


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
program bzoj_4006;
const qs=1023;
var channel:array[1..10]of longint;
num,lst:array[1..1000]of longint;
d:array[1..1000,0..1023]of longint;
l:array[1..6000]of record ed,pre,w:longint; end;
n,m,p,i,j,k,a,b,c,tot,hd,tl,status:longint;
q:array[1..qs]of longint;
v:array[1..qs]of boolean;
f:array[1..1023]of longint;
procedure link(a,b,w:longint);
begin
inc(tot);
l[tot].pre:=lst[a];
lst[a]:=tot;
l[tot].ed:=b;
l[tot].w:=w;
end;
procedure spfa(status:longint);
var i,k:longint;
begin
hd:=0;
tl:=n;
for i:=1 to n do q[i]:=i;
fillchar(v,sizeof(v),false);
for i:=1 to n do v[i]:=true;
while hd<>tl do
begin
hd:=hd mod qs+1;
k:=lst[q[hd]];
while k<>0 do
begin
if d[l[k].ed,status]>d[q[hd],status]+l[k].w then
begin
d[l[k].ed,status]:=d[q[hd],status]+l[k].w;
if not v[l[k].ed] then
begin
tl:=tl mod qs+1;
q[tl]:=l[k].ed;
v[l[k].ed]:=true;
end;
end;
k:=l[k].pre;
end;
v[q[hd]]:=false;
end;
end;
begin
readln(n,m,p);
tot:=0;
for i:=1 to m do
begin
readln(a,b,c);
link(a,b,c);
link(b,a,c);
end;
for i:=1 to p do channel[i]:=0;
for i:=1 to n do num[i]:=0;
for i:=1 to p do
begin
readln(a,b);
inc(channel[a],1<<(i-1));
num[b]:=i;
end;
fillchar(d,sizeof(d),$3f);
for j:=1 to 1<<p-1 do
begin
for i:=1 to n do
begin
if (num[i]<>0)and(1<<(num[i]-1)=j) then d[i,j]:=0;
k:=j and (j-1);
while k>0 do
begin
if d[i,k]+d[i,j-k]<d[i,j] then d[i,j]:=d[i,k]+d[i,j-k];
k:=j and (k-1);
end;
end;
spfa(j);
end;
for j:=1 to 1<<p-1 do
begin
status:=0;
f[j]:=maxlongint;
for i:=1 to p do if j and(1<<(i-1))<>0 then status:=status or channel[i];
for i:=1 to n do if d[i,status]<f[j] then f[j]:=d[i,status];
k:=j and (j-1);
while k<>0 do
begin
if f[k]+f[j-k]<f[j] then f[j]:=f[k]+f[j-k];
k:=j and (k-1);
end;
end;
writeln(f[1<<p-1]);
end.