P2170 选学霸

选学霸 - 洛谷

这个题目很简单，就是并查集+可行性dp

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define N 40010
#define INF 0x3f3f3f3f
int n,m,k,fa[N],size[N],dp[N],ans;

int Find (int x)
{
	if (x==fa[x]) return x;
	return fa[x]=Find (fa[x]);
}

void Merge (int x,int y)
{
	int r1=Find (x);
	int r2=Find (y);
	if (r1!=r2)
	{
		fa[r2]=r1;
		size[r1]+=size[r2];
		size[r2]=0;
	}
}

void Init ()
{
	scanf ("%d %d %d",&n,&m,&k);
	for (int i=1;i<=n;i++)
		fa[i]=i,size[i]=1;
	for (int i=1;i<=k;i++)
	{
		int x,y;
		scanf ("%d %d",&x,&y);
		Merge (x,y);
	}
}

void Work ()
{
	dp[0]=1;
	for (int i=1;i<=n;i++)
		if (i==Find (i))
			for (int j=2*m;j>=size[i];j--)
				if (dp[j-size[i]]==1) dp[j]=1;
	int ans=0;
	for (int i=1;i<=2*m;i++)
		if (abs (m-i)