首页 > 代码库 > [luogu P2170] 选学霸(并查集+dp)

[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开始向两边扫描寻找答案即可得解。

 

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int n,m,k,tot,que[20050],cnt[20050],father[20050],f[50050];
 7 
 8 int gf(int x) {
 9     if (father[x]==x) return x;
10     father[x]=gf(father[x]);
11     return father[x];
12 }
13 
14 int main() {
15     scanf("%d%d%d",&n,&m,&k);
16     for (int i=1; i<=n; i++) father[i]=i;
17     for (int i=1; i<=k; i++) {
18         int x,y;
19         scanf("%d%d",&x,&y);
20         int fx=gf(x);
21         int fy=gf(y);
22         if (fx!=fy) father[fx]=fy;
23     }
24     for (int i=1; i<=n; i++) cnt[gf(i)]++;
25     for (int i=1; i<=n; i++) if (cnt[i]) que[++tot]=i;
26     for (int i=1; i<=tot; i++) {
27         int cur=que[i];
28         for (int j=2*m; j>=cnt[cur]; j--)
29             f[j]=max(f[j],f[j-cnt[cur]]+cnt[cur]);
30     }
31     for (int i=0; i<=m; i++) {
32         if (f[m-i]==m-i) {
33             printf("%d",m-i);
34             break;
35         } 
36         if (f[m+i]==m+i) {
37             printf("%d",m+i);
38             break;
39         }
40     }
41 }

 

[luogu P2170] 选学霸(并查集+dp)