自动搬运

查看原文

来自洛谷，原作者为

	冷却心 111

搬运于2025-08-24 22:02:31，当前版本为作者最后更新于2024-11-26 21:06:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

性质 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;
}