此外,答案需要最优解的方案数,因此在过程中需要计算方案数,第一种过程不存在算重的情况,第二种过程存在算重的可能,但规定合并的顺序后即可避免算重。
定义 f[S][i] 表示以 i 为根、包含的关键点集合为 S 的斯坦纳树的<所需最小边数,最小边数对应方案数>,且这棵树的上一次构造过程(如果有)不是过程②。
定义 g[S][i] 表示以 i 为根、包含的关键点集合为 S 的斯坦纳树的<所需最小边数,最小边数对应方案数>。
所求即 g[包含所有关键点的集合][任意一个关键点],也可以是所有最优解的方案数之和除以最优解的点数,因为一棵无根的斯坦纳树对应点数棵有根的斯坦纳树,也即"边数加一"棵有根的斯坦纳树。
如果只考虑最小边数,则:
过程②相当于 g[S][i] ← f[T∪i][i] + g[(S-T)∪i][i],其中 T 包含 (S-i) 中的最小元素且 T 是 (S-i) 的子集。
过程①相当于 g[S][i] + 1 → f[S ∪ j][j] → g[S ∪ j][j],其中 i 和 j 直接相连。
由于过程①存在 g[S] 到 g[S] 的转移,但是转移的代价(边数)都是1,故可以根据 g[S][i] 的大小升序进行 BFS 转移。
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 51, maxd = 12, maxs = 1 << 12 | 1, mod = (int)1e9 + 7; int n, m, q, inv[maxn]; vector<int> e[maxn]; struct Info { int val, ways; void upd(Info const &t) { val > t.val && (val = t.val, ways = 0); val == t.val && (ways += t.ways) >= mod && (ways -= mod); } Info merge(Info const &t) const { int fir = val + t.val; if(fir >= n) return (Info){n, 0}; int sec = (LL)ways * t.ways % mod; return (Info){fir, sec}; } } f[maxs][maxn], g[maxs][maxn]; int tot, vis[maxn], dis[maxn], ord[maxn]; vector<int> adt[maxn]; int main() { inv[1] = 1; for(int i = 2; i < maxn; ++i) inv[i] = mod - (int)(mod / i * (LL)inv[mod % i] % mod); while(scanf("%d%d%d", &n, &q, &m) == 3) { for(int i = 0; i < n; ++i) vector<int>().swap(e[i]); while(q--) { int u, v; scanf("%d%d", &u, &v); --u; --v; e[u].push_back(v); e[v].push_back(u); } for(int i = 0; i < 1 << m; ++i) for(int j = 0; j < n; ++j) f[i][j] = g[i][j] = (Info){n, 0}; for(int i = 0; i < n; ++i) { int cur = i < m ? 1 << i : 0; f[cur][i] = g[cur][i] = (Info){0, 1}; } memset(vis, -1, n * sizeof(int)); for(int msk = 0; msk < 1 << m; ++msk) { for(int i = 0; i < n; ++i) { int cur = i < m ? 1 << i : 0; if(cur && !(msk & cur)) continue; int rem = msk ^ cur, lbt = rem & -rem; if(rem) for(int msk2 = (rem - 1) & rem; msk2; msk2 = (msk2 - 1) & rem) if(msk2 & lbt) { int u = msk2 | cur, v = (rem ^ msk2) | cur; g[msk][i].upd(f[u][i].merge(g[v][i])); } if(g[msk][i].val < n) adt[g[msk][i].val].push_back(i); } tot = 0; for(int i = 0, j = 0; i < n; ++i) { for(auto u : adt[i]) { if(vis[u] != msk) { vis[u] = msk; dis[u] = n; } if(dis[u] > i) { dis[u] = i; ord[tot++] = u; } } vector<int>().swap(adt[i]); for( ; j < tot; ++j) { int u = ord[j]; if(dis[u] > i) break; for(auto v : e[u]) { int cur = v < m ? 1 << v : 0; if(cur && !(msk & cur)) continue; if(vis[v] != msk) { vis[v] = msk; dis[v] = n; } if(dis[v] > dis[u] + 1) { dis[v] = dis[u] + 1; ord[tot++] = v; } } } } for(int i = 0; i < tot; ++i) { int u = ord[i]; for(auto v : e[u]) { int msk2 = msk | (v < m ? 1 << v : 0); Info tmp = g[msk][u]; ++tmp.val; f[msk2][v].upd(tmp); g[msk2][v].upd(tmp); } } } Info ans = (Info){n, 0}; for(int i = 0; i < n; ++i) ans.upd(g[(1 << m) - 1][i]); if(ans.val < n) { ans.ways = (LL)ans.ways * inv[ans.val + 1] % mod; printf("%d\n", ans.ways); } else { puts("0"); } } return 0; }最后送上一组能让赛场 AC 代码出错的数据:
祝你身体健康!5 4 3
2 3
4 5
4 1
2 5
全部评论
(2) 回帖