[題解]（水/并查集）luogu_P2170選學霸

佚名 6年前 (2019-04-16) 随笔 867人围观抢沙发百度已收录

很簡單的水題，因為智障沒有A所以發篇博客

同樣的題：luogu_P1455 搭配購買

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

用并查集維護一下所有實力相等的人的size，然而你可以選多個size......，於是跑個背包就行了，只要注意一下背包空間2m就完了

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=20010;
int n,m,k,ans,cnt;
int fa[maxn],size[maxn];
int v[maxn],f[maxn*2];
int abs(int a){
    return a<0?-a:a;
}
int find(int x){
    while(x!=fa[x])x=fa[x]=fa[fa[x]];
    return x;
}
void unionn(int x,int y){
    x=find(x),y=find(y);
    if(x==y)return;
    fa[x]=y;
    size[y]+=size[x];
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)fa[i]=i,size[i]=1;
    for(int i=1,a,b;i<=k;i++){
        scanf("%d%d",&a,&b);
        unionn(a,b);
    }
    for(int i=1;i<=n;i++){//存背包問題 
        if(fa[i]==i)v[++cnt]=size[i];
    }
    for(int i=1;i<=cnt;i++)
    for(int j=2*m;j>=v[i];j--)//因為可以多余選m個人，所以背包空間擴大為2m 
    f[j]=max(f[j],f[j-v[i]]+v[i]);
    int ans=0;
    for(int i=1;i<=2*m;i++){
        if(abs(ans-m)>abs(f[i]-m) || (abs(ans-m)==abs(f[i]-m) && ans>f[i]))ans=f[i];
    }
    printf("%d\n",ans);
}