[luogu] P1682 过家家 并查集

前言

传送门 :

并查集过程不怎么难,难的是如果处理两个集合之间的关系

就是普通的并查集也没带权什么的

思路

题意大致看完之后,会发现其实我们需要维护的是所有集合之中含有最少男孩的数量+k

但是我们怎么样维护 一个集合中既有男孩又有女孩的数量呢 ,

我们不妨尝试使用 v i s [ x ] [ y ] vis[x][y] vis[x][y]表示男孩 x x x,女孩 y y y,在合并的时候虽然男孩和女孩节点名字

相同但是我们任然可以直接合并,因为在我们计算的时候,我们只是使用女孩的而已

其实这题还是挺简单的(bushi 但是我选择的是维护男孩子的个数,女孩子的 s z sz sz考虑为0,从而使得很多细节都难调最后爆炸了

Mycode

const int N  = 260;
int p[N];
bool vis[N][N];
int a[N];

int n,m,k,f;

int ans = 0x3f3f3f3f;

int find(int x){
	if(p[x] !=x) return p[x] = find(p[x]);
	return p[x];
}



void solve()
{
	cin>>n>>m>>k>>f;
	for(int i=1;ix>>y;
		vis[x][y] = 1;
	}
	
	for(int i=1;i>x>>y;
		int fx = find(x);
		int fy = find(y);
		if(fx!=fy)
		p[fx] = fy;
	}
	
	for(int i=1;i