https://www.luogu.org/problemnew/show/P2170

并查集+DP

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn=20005;
int n,m,k,tot;
int p[maxn];
int man[maxn];
int f[maxn+maxn];
int find(int x) {return (x==p[x]?x:p[x]=find(p[x]));
}
void solve() {memset(f,0,sizeof(f));for(int i=1; i<=tot; i++)for(int j=2*m; j>=man[i]; j--)f[j]=max(f[j],f[j-man[i]]+man[i]);for(int i=0; i<=m; i++) {if(f[m-i]==m-i) {cout<<m-i<<endl;return;}if(f[m+i]==m+i) {cout<<m+i<<endl;return;}}return;
}
int main() {cin>>n>>m>>k;int u,v;for(int i=1; i<=n; i++)p[i]=i;for(int i=1; i<=k; i++) {cin>>u>>v;int x=find(u);int y=find(v);p[x]=y;}memset(man,0,sizeof(man));for(int i=1; i<=n; i++)man[find(i)]++;tot=0;for(int i=1; i<=n; i++)if(man[i]!=0) man[++tot]=man[i];solve();return 0;
}

?

轉載于:https://www.cnblogs.com/shandongs1/p/8215008.html

總結

以上是生活随笔為你收集整理的[Luogu] 选学霸的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。