Final Dash


冰茶姬+背包

题目

传送门：选学霸

考察要点：01背包、并查集

做法

首先把实力相同的全都用并查集并起来，把在每个集合的人数记录下来

然后就是背包问题了，注意，要使原来的M尽可能接近的选出学霸的数目，可能选多余m个人，所以把背包容量扩大为2m

代码

using namespace std;
#define INF 999999999
const int N=200000+1000;
int n,m,op,fat[N],p[N],ans[N],dp[N];
int pans=INF,Mins=INF;
int find(int x){
    if(fat[x]==x) return x;
    return fat[x]=find(fat[x]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>op;
    for(int i=1; i<=n; i++) fat[i]=i,p[i]=1;
    for(int i=1; i<=op; i++){
        int a,b; cin>>a>>b;
        int u=find(a),v=find(b);
        if(u!=v) fat[u]=v,p[v]+=u; //p[]记入集合元素个数
    }
    int kk=0;
    for(int i=1; i<=n; i++) //并查集后统计每个集合的数目
        if(fat[i]==i){
            kk++;
            ans[kk]=p[i];
        }
    for(int i=1; i<=kk; i++)
        for(int k=2*m; k>=ans[i]; k--)
            dp[k]=max(dp[k],dp[k-ans[i]]+ans[i]);
    for(int i=1; i<=2*m; i++) if(Mins>abs(dp[i]-m)) Mins=abs(dp[i]-m),pans=dp[i];
    if(pans==INF) cout<<0<<endl; //特别判断
    else cout<<pans<<endl;
    return 0;
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议