選學霸

​​傳送門​​

思路：

#include<bits/stdc++.h>
using namespace std;
const int mod = 1000007;
int f[40010];
int ans[40010];
int vis[40010];
int dp[40010];

int find(int x)
{
  if(f[x] != x)
  return f[x] = find(f[x]);
  return x;
}
int main()
{
  int n,m,k;
  cin>>n>>m>>k;
  for(int i = 1; i <= n; i++) f[i] = i;
  for(int i = 1; i <= k; i++)
  {
    int a,b;
    scanf("%d%d",&a,&b);
    f[find(a)] = find(f[b]);
  }
  for(int i = 1; i <= n; i++)
  {
    ans[find(f[i])]++;
  }
  int cnt = 1;
  for(int i = 1; i <= n; i++)
  {
    if(find(i) == i)
    {
      vis[cnt++] = ans[i];
    }
  }
  int res = 0x7f7f7f7f;
  int flag;
  for(int i = 1; i < cnt; i++)
  {
    for(int j = m*2; j >= vis[i]; j--)
    {
      dp[j] = max(dp[j-vis[i]]+vis[i],dp[j]);
    }
  }
  for(int i = 1; i <= 2*m; i++)
  {
    if(res > abs(m-dp[i]))
      {
        flag = dp[i];
        res = abs(m-dp[i]);
      }
  }
  printf("%d\n",flag);
}