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

Giorno_ · 2025-11-19 11:19:08 · 题解

题目大意：

有 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 个孩子，即他分配到的数字。

代码：

#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;
}