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

miller2014 · 2025-11-16 21:14:07 · 题解

题目传送门

1 具体思路

1.1 无解

如果一堆人，他们其中任意两个人都能直接或间接的得到对方的游戏机，且其中任意一个人都无法与不属于这堆人的人直接或间接的得到对方的游戏机，那么如果这堆人的人数比 k 小就无解。因为他们无法凑齐 k 个不同种类的游戏机。

1.2 有解

如果找到了一堆人，那么就将前 k 个人分别给予第 1,2,3 \dots k 种游戏机。其他人均给予第 k 种游戏机即可。

2 代码

2.1 无解

2.1.1 遍历

在判断之前，我们需要找出所有符合条件的一堆人。

void dfs(int x)
{
    vis[x]=1,sum++,g.push_back(x),ans[x]=min(k,sum);
    for(int i=0;i<e[x].size();i++)
        if(!vis[e[x][i]])
            dfs(e[x][i]);
}

2.1.2 判断

比较即可。

 for(int i=1;i<=n;i++)
        if(!vis[i])
        {
            sum=0,g.clear(),dfs(i);
            if(sum<k)return (cout<<"impossible")&&0;
        }

2.2 有解

输出遍历时统计的答案数组即可。

for(int i=1;i<=n;i++)cout<<ans[i]<<" ";

2.3ACcode

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m,k,sum,vis[N],ans[N];
vector<int>e[N],g;
void dfs(int x)
{
    vis[x]=1,sum++,g.push_back(x),ans[x]=min(k,sum);
    for(int i=0;i<e[x].size();i++)
        if(!vis[e[x][i]])
            dfs(e[x][i]);
}
int main()
{
    cin>>n>>m>>k;
    for(int a,b,i=1;i<=m;i++)
    {
        cin>>a>>b;
        e[a].push_back(b),e[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
        if(!vis[i])
        {
            sum=0,g.clear(),dfs(i);
            if(sum<k)return (cout<<"impossible")&&0;
        }
    for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
    return 0;
}