[luogu P2170] 选学霸（并查集+dp）

题目传送门：https://www.luogu.org/problem/show?pid=2170

题目描述

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

输入输出格式

输入格式：

第一行，三个正整数N，M，K。

第2...K行,每行2个数，表示一对实力相当的人的编号(编号为1…N)

输出格式：

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

输入输出样例

输入样例#1：

4 3 2
1 2
3 4

输出样例#1：

2

说明

100%的数据N，P<=20000

利用并查集将所有实力相当的人并到一个集合当中，把每个集合看做一个物品，物品的价值为每个集合中的人数，进而转换为01背包问题，由于是使价值总和与m的差的绝对值最小，于是利用2*m容量的背包，dp即可。

状态转移方程：f[j]=max(f[j],f[j-cnt[i]]+cnt[i])。

从m开始向两边扫描寻找答案即可得解。

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int n,m,k,tot,que[20050],cnt[20050],father[20050],f[50050];

int gf(int x) {
    if (father[x]==x) return x;
    father[x]=gf(father[x]);
    return father[x];
}

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++) {
        int x,y;
        scanf("%d%d",&x,&y);
        int fx=gf(x);
        int fy=gf(y);
        if (fx!=fy) father[fx]=fy;
    }
    for (int i=1; i<=n; i++) cnt[gf(i)]++;
    for (int i=1; i<=n; i++) if (cnt[i]) que[++tot]=i;
    for (int i=1; i<=tot; i++) {
        int cur=que[i];
        for (int j=2*m; j>=cnt[cur]; j--)
            f[j]=max(f[j],f[j-cnt[cur]]+cnt[cur]);
    }
    for (int i=0; i<=m; i++) {
        if (f[m-i]==m-i) {
            printf("%d",m-i);
            break;
        } 
        if (f[m+i]==m+i) {
            printf("%d",m+i);
            break;
        }
    }
}