[Luogu2170]选学霸

这一道题，由于他说，“如果实力相当的人中，一部分被选上，另一部分没有，同学们就会抗议。”而要求“既不让同学们抗议，又与原来的M尽可能接近”。因此，我们要对实力相当的一组同学必须全部选择。所以，我们需要先使用一个并查集，对这个无向图进行“缩点”，存下每一组学霸的人的数量。

我们在并查集的Union操作中，可以顺带就把每一组的学霸也Union过去，具体实现看代码。

然后，我们得到一些组的学霸。然后，我们把它转化成一个装箱问题。如果有可以刚好选满的，我们就把他和Min比较，如果比Min小，我们就记录下来。至于题目要求的“。(如果有两种方案与M的差的绝对值相等，选较小的一种:)”，其实可以很自然地。因为两次相等的话，前面就已经标记过了，不会在执行后面的了。

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

#define rep(i,a,n) for(register int i=(a);i<=(n);++i)

#define per(i,a,n) for(register int i=(a);i>=(n);--i)

#define fec(i,x) for(register int i=head[x];i;i=Next[i])

#define debug(x) printf("debug:%s=%d\n",#x,x)

#define mem(a,x) memset(a,x,sizeof(a))

template<typename A>inline void read(A&a){a=0;int f=1,c=0;while(c<'0'||c>'9'){c=getchar();if(c=='-')f*=-1;}while(c>='0'&&c<='9'){a=a*10+c-'0';c=getchar();}a*=f;}

template<typename A,typename B>inline void read(A&a,B&b){read(a);read(b);}

template<typename A,typename B,typename C>inline void read(A&a,B&b,C&c){read(a);read(b);read(c);}

template<typename A>A gcd(const A&m,const A&n){return m%n==0?n:gcd(n,m%n);}

const int maxn=20000+7,INF=0x7fffffff;

int n,m,k;

int x,y,ans=INF,Min=INF;

int father[maxn];

int f[maxn];

int cnt[maxn],tot;

int num[maxn];

int find(int x){

	return father[x]==x?x:father[x]=find(father[x]);

}

inline void unionn(int x,int y){

	int xx=find(x),yy=find(y);

	if(xx==yy)return;//这一句话非常重要！如果没有这句话，若xx==yy，cnt[xx]就会被重复计算以后被清零！

	father[yy]=xx;

	cnt[xx]+=cnt[yy];

	cnt[yy]=0;

}

inline void UFS_init(){

	rep(i,1,n)father[i]=i,cnt[i]=1;

}

void CC(){

	rep(i,1,n)if(cnt[i])num[++tot]=cnt[i];

}

void dp(){

	rep(i,1,tot)

		per(j,n,num[i])

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

}

void Init(){

	read(n,m,k);

	UFS_init();

	rep(i,1,k){

		read(x,y);

		unionn(x,y);

	}

}

void Work(){

	CC();

	dp();

	rep(i,0,n)if(f[i]==i&&abs(f[i]-m)<Min)Min=abs(f[i]-m),ans=f[i];//注意从零开始循环，0也是一个正解！

	printf("%d\n",ans);

}

int main(){

	Init();

	Work();

	return 0;

}

巴特西

[Luogu2170]选学霸

最新文章

热门文章