P4674 [BalticOI 2016 day1] Bosses Solution

· · 题解

首先如果这棵树已知，我们考虑怎么求出薪水总和。每位上司的薪水必须大于其直接下属薪水之和，那我们就令其等于下属薪水之和加一，然后手玩可得每个点最少应付的薪水是其子树的大小。

性质 1：已知这棵树时，每个点至少付的薪水是其子树大小。

证明：可以使用类似归纳法。

  • 首先这个结论对叶子结点显然成立，付一份薪水；
  • 然后考虑一个非叶子结点，如果他的子节点都满足这个结论，那么他需要的薪水至少是这些子节点的子树大小之和再加 1，也就是自己的子树大小，也满足。

所以得证。

性质 2：若已知这个树，则最小薪水总和为每个点的深度之和。

证明：首先根据上面的说明有，每个点的最小薪水是其子树大小，那么最小总和就是子树大小的和。考虑每个点只会对它以及它的祖先的子树大小产生贡献，一共有深度 d 个祖先（包括自己）所以贡献就是 d。那么总和就是深度之和。

所以把题目给的“可以接受的上司列表”转换为上司向下属连边的话，答案就是这张有向图的一个有根生成树（其实是树形图），要求所有节点深度之和最小。

注意到 n\leq 5000，考虑 O(n^2) 做法。枚举树根，主要在于如何寻找以它为根的深度之和最小的生成树。这里使用 bfs 寻找生成树。

性质 3：bfs 得到的树一定不劣。

证明：（也可能仅仅算感性说明）原因是所求的最小总和即为深度最小总和，而最小的深度就是结点到根的最短路，而 bfs 可以 O(n) 处理无权最短路，所以可以直接做。最后对每个点 bfs 出的生成树深度之和取最小值即可。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 5e3 + 10;
int n; vector<int> G[N];
int depth[N];
int BFS(int S) {
    for (int i = 1; i <= n; i ++) depth[i] = 0;
    queue<int> q; q.push(S); depth[S] = 1; int cnt = 0, sum = 0;
    while (!q.empty()) {
        ++ cnt; int u = q.front(); sum += depth[u]; q.pop();
        for (int v : G[u]) if (!depth[v]) {
            depth[v] = depth[u] + 1; q.push(v);
        }
    } return (cnt < n ? 2e9 : sum);
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        int m; cin >> m;
        for (int j = 1, u; j <= m; j ++) {
            cin >> u; G[u].emplace_back(i);
        }
    } int Ans = 2e9;
    for (int i = 1; i <= n; i ++)
        Ans = min(Ans, BFS(i));
    cout << Ans;
    return 0;
}