竞赛讨论区 > 牛客网暑期ACM多校训练营(第一场)G 题解
头像
tangjz
编辑于 2018-07-20 18:36
+ 关注

牛客网暑期ACM多校训练营(第一场)G 题解

构造有根斯坦纳树的过程包括①添加新的根连向原树的根②合并两棵具有相同根的树。在记录子树信息的基础上,这两个过程可以用动态规划加速。
此外,答案需要最优解的方案数,因此在过程中需要计算方案数,第一种过程不存在算重的情况,第二种过程存在算重的可能,但规定合并的顺序后即可避免算重。
定义 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) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐