[luogu] P2170 选学霸 01背包+并查集

前言

WA了两发才过,罚时罚到骨子里了

传送门 :

思路

显然这和那个买云朵差不多,看完题目大概就知道是 并查集+01背包了

不过这个并查集多维护一个 集合的大小罢了

不过里面有两个坑点:

• 选出的方案是可以超过体积的 所以大小需要 2 ∗ m 2*m 2∗m
• 还需要对每一个集合进行离散化(不可以直接size[i] ==0 continue) 原因未知。。

CODE

// Problem: P2170 选学霸
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2170
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

//��һ�δ��Ϻ�վ֮�� ��Ϊʹ��#define int long long TLE���¿��˺ܾõ�ʱ�� ���˼���ģ��
//����ʹ�ø��ӵ�ģ��

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define ll long long
#define endl '\n'


typedef pair pii;
map mp;

const int N  = 2e4+10;
int size1[N],p[N];
int f[N*2];

int find(int x)
{
	if(p[x]!=x)return p[x] = find(p[x]);
	return p[x];
}
void un(int a,int b)
{
	int pa = find(a);int pb = find(b);
	if(pa!=pb)
	{
		p[pa] = pb;
		size1[pb]+=size1[pa];
	}
}

int n,m,k;
void init()
{
	for(int i=1;i>n>>m>>k;
	init();
	
	while(k -- )
	{
		int a,b;
		cin>>a>>b;
		un(a,b);
	}
	
	int cnt= 0 ;
	
	for(int i=1;i