「LuoguP2170」选学霸（01背包

Description

老师想从N名学生中选M人当学霸，但有K对人实力相当，如果实力相当的人中，一部分被选上，另一部分没有，同学们就会抗议。所以老师想请你帮他求出他该选多少学霸，才能既不让同学们抗议，又与原来的M尽可能接近

Input

第一行，三个正整数N，M，K。

第2…K行,每行2个数，表示一对实力相当的人的编号(编号为1…N)

Output

一行，表示既不让同学们抗议，又与原来的M尽可能接近的选出学霸的数目。(如果有两种方案与M的差的绝对值相等，选较小的一种:)

Sample Input

4 3 2
1 2
3 4

Sample Output

Hint

100%的数据N，P<=20000

题解

用并查集把一起的合起来

构建背包模型价值和体积相同

然后跑两遍01背包一遍体积为m 另一遍体积为n-m(ans=n-f[n-m])

然后比较两个ans和m的差值大小关系按要求输出

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

int fa[20007],bel[20007];

int n,m,k;

int fifa(int x)

{

    if(fa[x]==x)return x;

    return fa[x]=fifa(fa[x]);

}

void con(int x,int y)

{

    int u=fifa(x),v=fifa(y);

    if(u!=v)fa[u]=v;

    return;

}

int s[20007];

int tos=0;

void scan()

{

    scanf("%d%d%d",&n,&m,&k);

    for(int i=1;i<=n;++i)fa[i]=i;

    int x,y;

    for(int i=1;i<=k;++i)

    {

        scanf("%d%d",&x,&y);

        con(x,y);

    }

    for(int i=1;i<=n;++i)

    {

        fifa(i);

        bel[fa[i]]++;

    }

    for(int i=1;i<=n;++i)

    if(bel[i])s[++tos]=bel[i];

    return;

}

int f[20007];

void dp()

{

    /*

    for(int i=1;i<=tos;++i)

    cout<<s[i]<<" ";

    cout<<endl;

    */

    for(int i=1;i<=tos;++i)

    for(int j=m;j>=s[i];--j)

    f[j]=max(f[j],f[j-s[i]]+s[i]);

    int ans1=f[m];

    memset(f,0,sizeof(f));

    for(int i=1;i<=tos;++i)

    for(int j=n-m;j>=s[i];--j)

    f[j]=max(f[j],f[j-s[i]]+s[i]);

    int ans2=n-f[n-m];

    //cout<<ans1<<" "<<ans2<<endl;

    if(m-ans1<=ans2-m)cout<<ans1;

    else cout<<ans2;

    return;

}

int main()

{

    scan();

    dp();

}

巴特西

「LuoguP2170」选学霸（01背包

Description

Input

Output

Sample Input

Sample Output

Hint

题解

最新文章

热门文章

巴特西

「LuoguP2170」 选学霸（01背包

Description

Input

Output

Sample Input

Sample Output

Hint

题解

最新文章

热门文章

「LuoguP2170」选学霸（01背包