BZOJ

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.