T657321 不能说的秘密 题解

· · 个人记录

n \le 10

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

k = 0

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

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

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

a_1 = a_2 = ... = a_n

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

正解

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

code

#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;
}