选学霸

题目

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

输入输出格式

输入格式

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

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

输出格式

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

输入输出样例

输入样例

4 3 2
1 2
3 4

输出样例

2

数据范围

100% N<=20000

思路

用并查集维护每个集合的元素个数

如果两个人实力相当则合并集合 同时更新集合内的个数

利用dp来判断选i个人是否可行 dp[i]表示选择i个人是否可行

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
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#define N 20005 * 2
using namespace std;
int n, m, k, f[N];
int size[N];
inline int find(int x){return f[x] < 0 ? x : f[x] = find(f[x]);}
int v[N], num;
bool dp[N];
int main()
{
scanf("%d%d%d",&n,&m,&k);
for (int i=1; i<=n; i++) f[i] = -1, size[i] = 1;
for (int i=1; i<=k; i++)
{
int a, b;
scanf("%d%d", &a, &b);
int aa = find(a), bb = find(b);
if (aa == bb) continue;
if (-f[aa] > -f[bb])
{
f[aa] += f[bb];
f[bb] = aa;
}
else
{
f[bb] += f[aa];
f[aa] = bb;
}
}
for (int i=1; i<=n; i++)
{
if (f[i] < 0) v[++ num] = -f[i];
}
dp[0] = 1; int tot = 0;
for (int i=1; i<=num; i++)
{
for (int j=n; j>=v[i]; j--)
if (dp[j-v[i]]) dp[j] = 1;
tot += v[i];
}
for (int i=0;;i++)
if(dp[m-i]){printf("%d\n",m-i);break;}
else if(dp[m+i]){printf("%d\n",m+i);break;}
return 0;
}