斯坦纳树


dp的意义代码中写的很清楚,唯一要注意的是,有一个卡常的地方,显然对于n个点m条边取k个点的斯坦纳树,我们的dp有意义开到dp[1<<k][n]吗? 这里是不必的,我们只需要开到dp[1<<(k-1)][n]即可,很容易想到dp[(1<<k)-1][any]中对于所有0<any<=k都是答案,然而却不一定能想到 dp[(1<<(k-1))-1][k]也是答案,借此我们可以提升50%的时空性能

牛客上的题目

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
#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
int k;

/**graph*/
struct star {
int v, nex;
} edge[1000 * 2];
int head[50], cnt, n, m;

void ini() {
cnt = -1;
for (int i = 0; i < n; i++) head[i] = -1;
}

void add_edge(int u, int v) {
edge[++cnt] = star{v, head[u]}, head[u] = cnt;
edge[++cnt] = star{u, head[v]}, head[v] = cnt;
}


/**dp*/
struct dpnode {
int w, ct;

dpnode(int w = 0, int ct = 0) : w(w), ct(ct) {}
};

dpnode dp[3][1 << 12][50];

// dp[0][s][i] 保证s联通的斯坦纳树的答案中 包含节点i的部分
// dp[1][s][i] 保证s联通 且 删除i节点以后依旧联通 的斯坦纳树的答案中 包含节点i的部分
// dp[2][s][i] 保证s联通 且 删除i节点以后不联通了 的斯坦纳树的答案中 包含节点i的部分
// if ( dp[1].w==dp[2].w ) dp[0]=merge(dp[1],dp[2])
// elif ( dp[1].w< dp[2].w ) dp[0]=dp[1]
// else dp[0]=dp[2]
dpnode dpmerge(dpnode a, dpnode b) {
return dpnode(a.w + b.w, 1ll * a.ct * b.ct % mod);
}

void upd(dpnode &a, dpnode b) {
if (b.w < a.w) a = b;
else if (b.w == a.w) {
a.ct = a.ct + b.ct;
if (a.ct >= mod) a.ct -= mod;
}
}


int main() {
while (~scanf("%d%d%d", &n, &m, &k)) {
ini();
for (int i = 0, u, v; i < m; i++) {
scanf("%d%d", &u, &v);
add_edge(u - 1, v - 1);
}
k--;
for (int s = 0; s < 1 << k; s++) {
for (int i = 0; i < n; i++) dp[0][s][i] = dp[1][s][i] = dp[2][s][i] = dpnode(1e9, 0);
}

for (int i = 0; i < k; i++) {
upd(dp[1][1 << i][i], dpnode(0, 1));
upd(dp[0][1 << i][i], dpnode(0, 1));
}
for (int s = 1; s < 1 << k; s++) {
for (int i = 0; i < n; i++) {
for (int s0 = (s - 1) & s; s0; s0 = (s0 - 1) & s) {//枚举s的非空真子集
if ((s0 & -s0) == (s & -s)) {// s0 必然包含s的最小的点
// upd(dp[2][s][i], dpmerge(dp[1][s0][i], dp[0][s ^ s0][i]));
upd(dp[0][s][i], dpmerge(dp[1][s0][i], dp[0][s ^ s0][i]));// type1
}
}
}
// dij
struct dijnode {
int w,id;

bool operator<(const dijnode &rhs) const { return w > rhs.w; }
};
priority_queue<dijnode> q;
for (int i = 0; i < n; i++) q.push(dijnode{dp[0][s][i].w, i});
while (!q.empty()) {
dijnode top = q.top(); q.pop();
if(top.w!=dp[0][s][top.id].w) continue;
for (int i = head[top.id]; ~i; i = edge[i].nex) {
if (top.w + 1 <= dp[0][s][edge[i].v].w) {
upd(dp[1][s][edge[i].v], dpmerge(dp[0][s][top.id], dpnode(1, 1)));
upd(dp[0][s][edge[i].v], dpmerge(dp[0][s][top.id], dpnode(1, 1))); // type2
q.push(dijnode{dp[0][s][edge[i].v].w, edge[i].v});
}
}
}
}
cout << dp[0][(1 << k) - 1][k].ct+1-1 << endl;
}
}

文章作者: fightinggg
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 fightinggg !
  目录