思路
转化题意, 问你在一个带权无向完全图中, 如何填上 \(w_i \in \left[1, \frac{n \cdot (n - 1)}{2} \right]\) , 使得其最小生成树上的边权为给定的 \(n - 1\) 个数
考虑模仿 \(\rm{kruskal}\) 的方式, 令 \(f_S\) 表示当前点集为 \(S\) , 每次转移, 如果当前边权需要在最小生成树中, 我们考虑连不联通的两点, 否则连联通的两点
这样只能通过 \(30 \%\) 的点
考虑优化
注意到我们其实不需要按照边来存储状态， 我们只需要知道连通块的大小即可, 考虑构造一种状态集合 \(\mathbb{S} = \{ (i, SZ_i) \}\) 表示大小为 \(SZ_i\) 的连通块有 \(i\) 个, 要求 \(\displaystyle \sum_{i = 1}^{\lvert \mathbb{S} \rvert} i \cdot SZ_i = n\)
这样我们对于每条树边才需要转移, 因为非树边不会对状态有影响
你发现状态的连通块个数顶多只有 \(\sqrt{n}\) 种, 再 \(\mathcal{O} (\sqrt{n})\) 求出变化后的状态, 需要转移 \(n\) 次, 枚举状态数 \(\mathcal{O} (n \mathop{P} (n))\) , 其中 \(\mathop{P} (n)\) 为分拆数
总时间复杂度 \(\mathcal{O} (n^2\sqrt{n}\mathop{P} (n))\) , 我认为可以通过
总结一下, 我们令 \(f_{i, \mathbb{S}}\) 表示考虑到第 \(i\) 条边, 当前的连通块状态为 \(\mathbb{S}\) 时的方案数, 令树边集合为 \(\mathbb{V}\)
\[f_{i, \mathbb{S}} = \begin{cases} \begin{aligned} & \sum_{a, b} \{ f_{i - 1, \mathbb{S}_{pre} } + SZ_a \cdot SZ_b , i \in \mathbb{V} \} \\ & f_{i - 1, \mathbb{S} } \cdot \sum_{j = 1}^{\lvert \mathbb{S} \rvert} \frac{SZ_j \cdot (SZ_j - 1)}{2} \end{aligned} \end{cases} \]当然具体实现中使用刷表法
实现
框架
首先你至少要把状态预处理出来, 然后就按照树边和非树边干就完了
代码
#include <bits/stdc++.h>
const int MAXM = 41 * 41;
const int MAXP = 37400;
const int MOD = 1e9 + 7;
int add(int a, int b) { return (a + b >= MOD) ? a + b - MOD : a + b; }
int dec(int a, int b) { return (a - b < 0) ? a - b + MOD : a - b; }
int mul(int a, int b) { return (1LL * a * b) % MOD; }
void pluson(int &a, int b) {a = add(a, b);}
int n;
bool V[MAXM];
std::map<std::vector<int>, int> S;
std::map<int, std::vector<int>> Sback;
std::vector<int> nowS, Snext;
int id = 0;
int C[MAXP];
void init(int x, int v){
if(v == 0) {
if(x == 0) {
S[nowS] = ++id, Sback[id] = nowS;
for(int i = 0; i < nowS.size(); i++) C[id] += nowS[i] * (nowS[i] - 1) / 2;
}
return ;
}
init(x, v - 1);
if(x >= v){
nowS.push_back(v);
init(x - v, v);
nowS.pop_back();
}
}
int f[MAXM][MAXP];
int main()
{
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int read; scanf("%d", &read);
V[read] = true;
}
int m = n * (n - 1) / 2;
/*初始化状态*/
init(n, n);
f[0][1] = 1;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= id; j++)
if (f[i - 1][j]) {
if (V[i]) {
nowS = Sback[j];
for (int a = 0; a < nowS.size(); a++)
for (int b = a + 1; b < nowS.size(); b++) {
Snext.clear();
Snext.push_back(nowS[a] + nowS[b]);
for (int k = 0; k < nowS.size(); k++)
if (k != a && k != b)
Snext.push_back(nowS[k]);
std::sort(Snext.begin(), Snext.end());
std::reverse(Snext.begin(), Snext.end());
pluson(f[i][S[Snext]], mul(f[i - 1][j], mul(nowS[a], nowS[b])));
}
}
else
pluson(f[i][j], mul(f[i - 1][j], C[j] - i + 1));
}
int Ans = 0;
for (int i = 1; i <= id; i++)
pluson(Ans, f[m][i]);
printf("%d", Ans);
return 0;
}
总结
善于模仿算法的实现方式
优化状态, 首先找到算法的本质, 然后只存储需要用到的性质, 本题中利用组合数学简化了一些状态, 具体的, 连边这一类问题, 通过连通块的组合数即可求出
标签：mathbb,SZ,int,T4,12.17,cdot,MOD,CW,nowS From： https://www.cnblogs.com/YzaCsp/p/18613459