题解：P14501 [NCPC 2025] Gotta Trade Some of 'Em

题目大意：

有

n

个孩子，

m

个朋友关系，朋友相同的孩子们被分在一个组里，有

k

个数字，求每个孩子的分配方案使得每个组至少包括数字

1 \sim k

。

思路：

把

m

个关系使用并查集合并，统计每组的孩子数，若当前组孩子数小于

k

，直接输出 impossible，因为不可能凑出

1 \sim k

。
定义

cnt_p

为组

p

内的孩子数。初始化默认每个孩子自己一组值为 1，合并时将两组值加和即可。
定义

ans_p

为组

p

所拥有的最大数字，那么当

ans_p = k

时说明本组已分配完毕包括数字

1 \sim k

。从 1 开始给组

p

分配数字，对于每次

ans_p < k

，令

ans_p

加 1，把

ans_p

的值赋给当前遍历的第

i

个孩子，即他分配到的数字。

代码：

CPP

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N = 1e5 + 10;
int ans[N];
int n,m,k;
int cnt[N],a[N],fa[N];
int find(int x){
	return x == fa[x]?x:fa[x] = find(fa[x]);
}
void mix(int x,int y){
	int fx = find(x),fy = find(y);
	fa[fx] = fy;//合并祖先 
	cnt[fy] += cnt[fx];//合并人数 
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n >> m >> k;
	for(int i = 1;i <= n;i ++){
		fa[i] = i;
		cnt[i] = 1;
	}
	for(int i = 1;i <= m;i ++){
		int x,y;
		cin >> x >> y;
		int fx = find(x),fy = find(y);
		if(fx != fy){
			mix(x,y);
		}
	}
	for(int i = 1;i <= n;i ++){
		int p = find(i);
		if(cnt[p] < k){
			puts("impossible");
			return 0;
		}
		if(ans[p] < k){//若当前组拥有数字不足 
			ans[p] ++;
		}
		a[i] = ans[p];//当前孩子分配到的数字 
	}
	for(int i = 1;i <= n;i ++)cout << a[i] << ' ';
	return 0;
}

题解：P14501 [NCPC 2025] Gotta Trade Some of 'Em

文章操作

题目大意：

思路：

代码：

相关推荐

评论

题解：P14501 [NCPC 2025] Gotta Trade Some of 'Em