「LuoguP2170」选学霸（01背包

mac2022-06-30 17

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(); }

转载于:https://www.cnblogs.com/qwerta/p/9379757.html

最新回复(0)

「LuoguP2170」 选学霸（01背包