专栏文章

T657321 不能说的秘密 题解

cchrisgr_pretty_girl
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio7m7w6
此快照首次捕获于
2025/12/02 14:41
3 个月前
此快照最后确认于
2025/12/02 14:41
3 个月前
查看原文

n≤10n \le 10

枚举哪些人和小 i 交朋友，然后check

k=0k = 0

发现任何人都不可能得到两个来源的小 i 的秘密，所以无论如何交朋友小 i 都不会从陌生人口中听见自己的秘密。直接贪心拿最大的 mm 个 aia_i。

k=n⋅(n−1)2k = \frac{n \cdot (n - 1)}{2}

任意两个人都是朋友，所以无论和任意大于等于2个人交朋友都会让其他人认为小 i 的秘密不是秘密，从而告诉小 i ，所以小 i 要么交一个朋友要么和 nn 个人都交朋友（若和 nn 个人都交朋友那就没有陌生人了，所以不会有陌生人告诉小 i 他的秘密）。所以只需要判断 mm 和 nn 的大小，输出 ∑i=1nai\sum_{i = 1}^n a_i 或 max⁡i=1nai\max_{i=1}^n a_i 即可。

a1=a2=...=ana_1 = a_2 = ... = a_n

和正解差不多，只不过做的是可行性01背包，具体可以看正解。

正解

由 k=n⋅(n−1)2k = \frac{n \cdot (n - 1)}{2} 的部分分可以发现一个朋友堆里要么只与一个人交朋友，要么和所有人都交朋友，要么都不交朋友，所以可以用并查集维护一下朋友堆，并对朋友堆做一个01背包。
不会并查集？那你还考啥啊，回家吧 可以维护一个 bookbook 数组（记录该点是否更新过答案）， 从 11 扫到 nn 若该点没更新过答案，就 dfsdfs 一下和他相连（直接和间接）朋友堆，并更新朋友堆的 bookbook。

code

CPP
#include<bits/stdc++.h>
using namespace std;
#define N 5005
int n, m, k, a[N], f[N], sum[N], mx[N], siz[N], ans[N];
inline int find(int x) { return x ^ f[x] ? f[x] = find(f[x]) : x; }
int main() {
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", a + i);
		sum[i] = mx[i] = a[i], siz[i] = 1, f[i] = i;
	}
	for(int i = k; i; --i) {
		int u, v;
		scanf("%d%d", &u, &v);
		int uu = find(u), vv = find(v);
		if(uu ^ vv) sum[uu] += sum[vv], siz[uu] += siz[vv], mx[uu] = max(mx[uu], mx[vv]), f[vv] = uu;
	}
	for(int i = n; i; --i) {
		int fa = find(i);
		if(fa == i) {
			--siz[fa], sum[fa] -= mx[fa];
			int g[N];
			memset(g, 0, sizeof(g));
			for(int j = m - 1; ~j; --j) g[j + 1] = ans[j] + mx[fa];
			for(int j = m; j > siz[fa]; --j) g[j] = max(g[j], g[j - siz[fa]] + sum[fa]);
			for(int i = m; ~i; --i) ans[i] = max(ans[i], g[i]);
		}
	}
	printf("%d", ans[m]);
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...