『题解』洛谷P2170 选学霸

更好的阅读体验

Portal

Portal1: Luogu

Description

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

Input

第一行，三个正整数\(N, M, K\)。

第\(2\)至\(K\)行，每行\(2\)个数，表示一对实力相当的人的编号（编号为\(1 \cdots N\)）。

Output

一行，表示既不让同学们抗议，又与原来的\(M\)尽可能接近的选出学霸的数目。（如果有两种方案与\(M\)的差的绝对值相等，选较小的一种）

Sample Input

4 3 2

1 2

3 4

Sample Output

2

Hint

对于\(100\%\)的数据\(N, P \le 20000\)。

Solution

这题如果选了一个人，那么与他实力相当的人也要选上。所以我们可以把会产生连锁反应的人都捆起来。不难想到用并查集。

然后我们把一捆一捆的总价值记录下来，做一遍01背包就好了。

Code

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

const int INF = 0x3f3f3f3f, MAXN = 20005;

int n, m, k, u, v, t[MAXN], w[MAXN], dp[MAXN], father[MAXN];

inline int find(int x) {//并查集

    return (x == father[x] ? x : father[x] = find(father[x]));

}

inline void Union(int u, int v) {//合并

    int p = find(u), q = find(v);

    if (p != q) father[p] = q;

}

int main() {

    scanf("%d%d%d", &n, &m, &k);

    for (int i = 1; i <= n; i++)

        father[i] = i;

    for (int i = 1; i <= k; i++) {

        scanf("%d%d", &u, &v);

        Union(u, v);//将输入的两个人合并起来

    }

    for (int i = 1; i <= n; i++)

        t[find(i)]++;

    int cnt = 0;

    for (int i = 1; i <= n; i++)

        if (t[i]) w[++cnt] = t[i];//计算价值

    for (int i = 1; i <= cnt; i++)

        for (int j = m << 1; j >= w[i]; j--)

            dp[j] = max(dp[j], dp[j - w[i]] + w[i]);//01背包

    int Min = INF, ans = 0;

    for (int i = 0; i <= m; i++) {

        if (dp[m - i] == m - i) {

            printf("%d\n", m - i);

            return 0;

        }

        if (dp[m + i] == m + i) {

            printf("%d\n", m + i);

            return 0;

        }

    }

    return 0;

}