Luogu-P2710-选学霸

Posted on Edited on Word count in article: 405

题目 P2170 选学霸

题目描述

老师想从 nn 名学生中选 mm 人当学霸，但有 kk 对人实力相当，如果实力相当的人中，一部分被选上，另一部分没有，同学们就会抗议。所以老师想请你帮他求出他该选多少学霸，才能既不让同学们抗议，又与原来的 mm 尽可能接近。

输入格式

第一行，三个正整数 n,m,kn,m,k。

接下来 kk 行，每行 22 个数，表示一对实力相当的人的编号（编号为 1,2,⋯n1,2,\cdots n）。

输出格式

共一行，表示既不让同学们抗议，又与原来的 mm 尽可能接近的选出学霸的数目。

如果有两种方案与 mm 的差的绝对值相等，选较小的一种。

思路：背包dp，并查集

实力相当的处理

如果有 xx 个人实力相当，可以考虑将这 xx 个人放到并查集中维护。

每新增一个实力相当的人，就放到对应的并查集中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int root[N];

int get(int x) {
    if(x != root[x]) {
        root[x] = get(root[x]);
        return root[x];
    } else
        return root[x];
}

void merge(int x, int y) {
    root[get(y)] = get(x);
}

void init() {
    for(int i = 1; i <= n; i++) {
        root[i] = i;
    }
}

学霸数目

经过上一步之后，成绩相当的人都在并查集中。

考虑每一个集合中的元素个数为花费，那么就可以转化为背包dp。

  • 建立一个 cntcnt 数组记录每个并查集中元素个数。

  • 在同一个并查集中的元素，计数到 cntcnt 数组的同一个位置。

  • 最后，cntcnt 数组中就是所有的花费。

之后，就是常规的0/1背包。

1
2
3
4
5
for(int i = 1; i < pt; i++) {
    for(int j = 2 * m; j >= cnt[i]; j--) {
        dp[j] |= dp[j - cnt[i]];
    }
}

最近数量

从 mm 向外出发，最近的一个数就是答案。

1
2
3
4
5
6
7
8
9
10
for(int i = 0;; i++) {
    if(dp[m - i]) {
        cout << m - i << endl;
        return 0;
    }
    if(dp[m + i]) {
        cout << m + i << endl;
        return 0;
    }
}

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
// template v11
#include <bits/stdc++.h>
#define set(x, y) memset(x, y, sizeof x)

using namespace std;
using ll = long long;

const int inf = 0x7f7f7f7f;

const int N = 2e4 + 10;

int n, m, k;
int root[N];
int head[N];
int cnt[N];
bool dp[2 * N];
int pt = 1;

int get(int x) {
    if(x != root[x]) {
        root[x] = get(root[x]);
        return root[x];
    } else
        return root[x];
}

void merge(int x, int y) {
    root[get(y)] = get(x);
}

void init() {
    for(int i = 1; i <= n; i++) {
        root[i] = i;
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("diyi.in", "r", stdin);
    freopen("diyi.out", "w", stdout);
#endif
    cin >> n >> m >> k;
    int t1, t2;
    init();
    for(int i = 0; i < k; i++) {
        cin >> t1 >> t2;
        if(get(t1) != get(t2))
            merge(t1, t2);
    }
    for(int i = 1; i <= n; i++) {
        int r = get(i);
        if(!head[r]) {
            head[r] = pt;
            pt++;
        }
        cnt[head[r]]++;
    }
    dp[0] = true;
    for(int i = 1; i < pt; i++) {
        for(int j = 2 * m; j >= cnt[i]; j--) {
            dp[j] |= dp[j - cnt[i]];
        }
    }
    for(int i = 0;; i++) {
        if(dp[m - i]) {
            cout << m - i << endl;
            return 0;
        }
        if(dp[m + i]) {
            cout << m + i << endl;
            return 0;
        }
    }
    return 0;
}