题目相关

题目链接: 洛谷 P2170 选学霸

题目描述

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

输入格式

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

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

输出格式

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

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

样例 #1

样例输入 #1

1
2
3
4 3 2
1 2
3 4

样例输出 #1

1
2

提示

对于 $100%$ 的数据，满足 $1 \le n,m \le 2 \times 10^4$。

题目解析

如果一组人的实力相同，那么他们所有人要么全选，要么不选，无法分割。可以用并查集来将所有人分成这样的组。

那么自然可以联想到背包 dp 中物品不可分的特性，实力相同的人不妨视为一个物品，其质量即为人数。

那么问题就转变为：求一种背包方案，使得其质量与 $m$ 尽量接近。这是一个经典的可行性背包问题。

设 $f(i,j)=0/1$ 表示前 $i$ 个物品中，是否存在一种背包方案，使得其质量和为 $j$。那么状态转移为：

  1. $f(0,0) = 1$，什么都不装是合法背包状态；
  2. $f(i,j) = f(i-1,j) | f(i-1,j-w_i)$，其中 $w_i$ 表示第 $i$ 件物品的质量，该物品由装或不装两个状态转移而来，若其中一个状态可行，则目前背包状态可行。

背包问题存在通用的倒序枚举方法省去第一维，也可以使用滚动数组解决（其实倒序枚举也算是滚动数组）。

需要注意的是本题质量可以超过 $m$，因此 dp 数组的大小应该计算到 $2m$。

代码

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib> 
using namespace std;

const int maxn = 200100;
int n, m, k;
int fa[maxn];
int f[2 * maxn];
int group_num[maxn];
int group[maxn], tot;

int find_fa(int x){
    return (fa[x] == x) ? x : fa[x] = find_fa(fa[x]);
}

int main() {
    // read input
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
    }

    // read connection & create dsu
    int rx, ry, fx, fy;
    for (int i = 1; i <= k; ++i) {
        scanf("%d%d", &rx, &ry);
        fx = find_fa(rx);
        fy = find_fa(ry);
        if (fx != fy) {
            fa[fx] = fy;
        }
    }

    // calculate group & convert to dp item
    for (int i = 1; i <= n; ++i) {
        ++group_num[find_fa(i)];
    }
    for (int i = 1; i <= n; ++i) {
        if (group_num[i]) {
            group[++tot] = group_num[i];
        }
    }

    // dp
    f[0] = 1;
    for (int i = 1; i <= tot; ++i) {
        for (int j = 2 * m; j >= group[i]; --j) {
            f[j] |= f[j - group[i]];
        }
    }

    // output answer
    for (int i = 0; i <= m; ++i) {
        if (f[m - i]) {
            printf("%d", m - i);
            exit(0);
        }
        if (f[m + i]) {
            printf("%d", m + i);
            exit(0);
        }
    } 

    return 0;
}