洛谷P2170选学霸（玄学吧）

玄学吧）"/>

洛谷P2170选学霸（玄学吧）

题目描述

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

输入输出格式

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

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

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

输入输出样例

4 3 2
1 2
3 4

2

说明

100%的数据N，P<=20000

冷静分析（滑稽）：

某人说这题用tarjan求强连通分量......emmm......不适合我这种萌新，所以很自然地想到并查集（一点也不自然），用并查集把程度相当的学生放在一个集团中，再把每个集团当做一个物品，把m当做背包容量，只要注意题意是选出的人数和m的差值最小，所以说是个魔改01背包

代码大概这个样子：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<set>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;
int k,n,m,x,y,fa[20100],f[50100];
int num[20100],item[20100];
int Find(int x)
{
return (x==fa[x]?x:fa[x]=Find(fa[x]));
}
void Union(int x,int y)
{
int r1=Find(x);
int r2=Find(y);
if(r1!=r2)
{
fa[r1]=r2;
}
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
{
fa[i]=i;
}
for(int i=1;i<=k;i++)
{
scanf("%d%d",&x,&y);
Union(x,y);
}
memset(num,0,sizeof(num));
for(int i=1;i<=n;i++)
{
num[Find(i)]++;
}
int cnt=0;
for(int i=1;i<=n;i++)
{
if(num[i]!=0)
{
item[++cnt]=num[i];
}
}
memset(f,0,sizeof(f));
for(int i=1;i<=cnt;i++)
{
for(int j=2*m;j>=item[i];j--)
{
f[j]=max(f[j],f[j-item[i]]+item[i]);
}
}
for(int i=0;i<=m;i++)
{
if(f[m-i]==m-i)
{
printf("%d",m-i);
return 0;
}
if(f[m+i]==m+i)
{
printf("%d",m+i);
return 0;
}
}
    return 0;    
}