[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[],cnt[],father[],f[];

 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=; i<=n; i++) father[i]=i;

     for (int i=; 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=; i<=n; i++) cnt[gf(i)]++;

     for (int i=; i<=n; i++) if (cnt[i]) que[++tot]=i;

     for (int i=; i<=tot; i++) {

         int cur=que[i];

         for (int j=*m; j>=cnt[cur]; j--)

             f[j]=max(f[j],f[j-cnt[cur]]+cnt[cur]);

     }

     for (int i=; 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;

         }

     }

 }