题解：P17194 [KOI 2026 #2] 分发零食

wanganze · 2026-08-07 15:50:54 · 题解

题意

有 n 个人和 n 种零食各一份，每个人有若干喜欢的零食。每个人进入房间后会拿走所有喜欢的零食，求一种让每个人进入房间的顺序使每个人都拿到喜欢的零食或报告无解。

分析

类似拓扑排序，我们记录每个人喜欢的零食还剩多少，将喜欢零食的只剩一个（度数为 1）的入队。对于队列中的每个人，我们找到这种剩下的零食并选取，然后更新其他喜欢这种零食的人的度数，并把度数为 1 的人入队。

这样贪心是正确的。考虑任意合法的方案，没拿过的人里第一个拿一定只剩一个喜欢的零食，否则他一次会拿走至少两个零食，让别人拿不到零食。如果有多人只剩一个喜欢的零食，如果喜欢的互不相同顺序显然没关系，否则一定会冲突，谁先取最后都凑不齐。

考虑复杂度。每个人最多入队一次，因此每个人的每种喜欢的零食最多遍历一次。又因为每个人的度数最多只会减 C_i 次，所以总复杂度 O(n + \sum C_i)。

实现

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
vector<int> e[N],g[N],res;
int d[N];
bool st[N];
int main()
{
    int n;
    cin>>n;
    for(int i = 1,x; i <= n; i ++)
    {
        cin>>d[i];
        for(int j = 1; j <= d[i]; j ++) cin>>x,e[i].push_back(x),g[x].push_back(i);
    }
    queue<int> q;
    for(int i = 1; i <= n; i ++)
        if(d[i] == 1) q.push(i);
    while(q.size())
    {
        int t = q.front();
        q.pop();
        for(auto x : e[t])
            if(!st[x])
            {
                res.push_back(t);
                st[x] = 1;
                for(auto y : g[x])
                    if(-- d[y] == 1) q.push(y);
                break;
            }
    }
    if(res.size() != n)
    {
        cout<<"-1\n";
        return 0;
    }
    for(auto x : res) cout<<x<<' ';
    cout<<'\n';
    return 0;
}