```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int f[20020],dp[20020],num[20020],a[20020];
int finds(int u){
if(f[u]==u) return u;
f[u]=finds(f[u]);
return f[u];
}
bool cmp(int u,int v){
return u>v;
}
int main(){
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++) f[i]=i,num[i]=1;
for(int i=1;i<=k;i++){
int u,v;
scanf("%d%d",&u,&v);
if(finds(u)!=finds(v)) num[f[v]]+=num[f[u]],f[f[u]]=f[v];
}
int cnt=0;
for(int i=1;i<=n;i++){
if(finds(i)==i){
a[++cnt]=num[i];
}
}
sort(a+1,a+1+cnt,cmp);
//for(int i=1;i<=cnt;i++) cout<<a[i]<<' ';
for(int i=1;i<=cnt;i++){
for(int j=m*2;j>=1;j--){
if(j>a[i])
dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
}
}
int ans=2e9;
for(int i=m*2;i>=0;i--){
if(abs(m-dp[i])<abs(ans-m)) ans=dp[i];
}
cout<<ans;
return 0;
}
```
by 2017czhang @ 2018-10-30 18:07:31
ans那一段去掉,并把状态转移方程加个“不选择该状态”的转移方式。
比如dp[i]=dp[i-1];
by R·Dali @ 2019-11-02 11:40:49