题解：AT_arc057_d [ARC057D] 全域木

· · 题解

思路

转化题意，问你在一个带权无向完全图中，如何填上 w_i \in \left[1, \frac{n \cdot (n - 1)}{2} \right]，使得其最小生成树上的边权为给定的 n - 1 个数。

考虑模仿 kruskal 的方式，令 f_S 表示当前点集为 S，每次转移，如果当前边权需要在最小生成树中，我们考虑连不联通的两点，否则连联通的两点。

这样只能通过 30 \% 的点。

考虑优化。

注意到我们其实不需要按照边来存储状态，我们只需要知道连通块的大小即可，考虑构造一种状态集合 \mathbb{S} = \{ SZ_i \} 表示大小为 SZ_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}， i \notin \mathbb{V} \end{aligned} \end{cases}

当然具体实现中使用刷表法。

解释一下，对于树边，我们枚举两个不同的连通块处理；对于非树边，我们只需要预处理出每种状态的 \displaystyle\sum_{j = 1}^{\lvert \mathbb{S} \rvert} \frac{SZ_j \cdot (SZ_j - 1)}{2}， i \notin \mathbb{V} 即可。

实现

框架

首先你至少要把状态预处理出来，然后就按照树边和非树边干就完了。

代码

#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 dfs(int x, int v, int aim) {
    if (x == 0 && v == aim) {
        S[nowS] = ++id, Sback[id] = nowS;
        for(int i = 0; i < nowS.size(); i++) C[id] += nowS[i] * (nowS[i] - 1) / 2;
        return ;
    }

    if (x >= v && v != 0) {
        int len = nowS.size();
        for (int i = 0; i < len; i++) nowS[i]++;
        dfs(x - v, v, aim);
        for (int i = 0; i < len; i++) nowS[i]--;
    }

    if (x >= 1) {
        nowS.push_back(1);
        dfs(x - 1, v + 1, aim);
        nowS.pop_back();
    }
}

int m;

int f[MAXM][MAXP];
void solve()
{
    f[0][id] = 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 main()
{
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int read; scanf("%d", &read);
        V[read] = true;
    }
    m = n * (n - 1) / 2;

    /*初始化状态*/
    for (int i = 1; i <= n; i++)
        dfs(n, 0, i);

    solve();

    int Ans = 0;
    for (int i = 1; i <= id; i++)
        pluson(Ans, f[m][i]);
    printf("%d", Ans % MOD);

    return 0;
}

总结

善于模仿算法的实现方式。

优化状态，首先找到算法的本质，然后只存储需要用到的性质，本题中利用组合数学简化了一些状态，具体的，连边这一类问题，通过连通块的组合数即可求出。