codevs 3372 选学霸

3372 选学霸

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 大师 Master

题目描述 Description

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

输入描述 Input Description

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

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

输出描述 Output Description

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

样例输入 Sample Input

4 3 2

1 2

3 4

样例输出 Sample Output

数据范围及提示 Data Size & Hint

100%的数据N，P<=30000

【思路】

将实力相同的人放到一个并查集里，看做一件物品，人数相当于这个物品的体积，再01背包；

因为对于每件物品要么不选要么选这实力相当的一帮人；

要求绝对值最小背包容积扩大两倍

但是由于这里问的是相差最小，即绝对值最小，所以这个背包空间要开两倍，然后在从容量满的那个点，向左向右同时进行查找，输出第一个答案

【代码】

#include<iostream>

#include<cstdio>

#include<cstdlib>

using namespace std;

int far[],cnt[],ans[],fd[];

int f(int x)

{

    return far[x]==x?x:f(far[x]);

}

int main()

{

    int n,m,k;

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

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

    {

        far[i]=i;

        cnt[i]=;

    }

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

    {

        int p,q;

        scanf("%d%d",&p,&q);

        int xf=f(p),yf=f(q);

        if(xf!=yf)

        {

            far[xf]=yf;

            cnt[yf]+=cnt[xf];

            cnt[xf]=;

        }

    }

    int js=;

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

    {

        if(cnt[i])

        ans[++js]=cnt[i];

    }

    for(int i=;i<=js;i++)

    {

        for(int j=*m+;j>=ans[i];j--)

        {

            fd[j]=max(fd[j],fd[j-ans[i]]+ans[i]);

        }

    }

  for(int i=;i<=m;i++)

  {

      if(fd[m-i]==m-i)

      {

          cout<<m-i<<endl;

          break;

      }

      if(fd[m+i]==m+i)

      {

          cout<<m+i<<endl;

          break;

      }

  }

    return ;

}

巴特西

codevs 3372 选学霸

3372 选学霸

最新文章

热门文章