[USACO13JAN] Party Invitations S

GitHub跳转原题关系图返回列表

把已邀请奶牛作为传播源，用队列维护新邀请的奶牛，并在每个组只剩一头未邀请时触发继续邀请。

OJ: luogu

题目 ID: P3068

难度:普及/提高-

标签:队列模拟图论

日期: 2026-06-18 19:00

目录

  1. 题意
  2. 思路
    1. 样例传播过程
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

有 n 头牛和 m 个朋友组。
如果一个大小为 k 的组里已经邀请了至少 k-1 头牛，那么最后那头牛也必须被邀请。

现在一开始必须邀请 1 号牛，问在这些约束不断触发后，最少需要邀请多少头牛。
特别注意：大小为 1 的组会在初始时直接触发，因为此时已经邀请了 0=k-1 头牛。

思路

先看一个直接模拟闭包的朴素解：

cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> groups(m + 1);
    for (int group_id = 1; group_id <= m; ++group_id) {
        int size;
        cin >> size;
        groups[group_id].resize(size);
        for (int i = 0; i < size; ++i) {
            cin >> groups[group_id][i];
        }
    }

    vector<int> invited(n + 1, 0);
    invited[1] = 1;

    bool changed = true;
    while (changed) {
        changed = false;

        for (int group_id = 1; group_id <= m; ++group_id) {
            int not_invited_count = 0;
            int last_cow = 0;

            for (int cow : groups[group_id]) {
                if (!invited[cow]) {
                    ++not_invited_count;
                    last_cow = cow;
                }
            }

            if (not_invited_count == 1) {
                invited[last_cow] = 1;
                changed = true;
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (invited[i]) ++ans;
    }

    cout << ans << '\n';
    return 0;
}

朴素做法每一轮都检查所有组：如果某个组只剩一头牛没被邀请，就把它邀请进来。
这样容易理解，但会反复扫描所有组，数据大时不够高效。

更好的做法是只在“有新牛被邀请”时，更新它所在的那些组。

对每个组维护一个 rest_count，表示这个组里还没有被邀请的牛有多少头。
当一头牛 cow 被邀请后，只会影响包含 cow 的组。于是遍历 belong[cow]：

  • 对每个组的 rest_count 减一；
  • 如果减完后变成 1，说明这个组已经满足“邀请了 k-1 头”的触发条件；
  • 再找出组里最后那头没被邀请的牛，把它加入队列。

队列里存的是“刚刚被邀请、还没用来更新组”的牛。
这个流程和 rbook 的 队列 文章里的“逐层扩展”模型一致：新状态入队，队头状态依次扩展。

初始化时，除了 1 号牛以外，所有大小为 1 的组里的牛也要先入队。

样例传播过程

这张表展示样例中邀请是如何被组约束一步步触发的。

已邀请新牛 被影响的组 触发结果
1 {1,3} 组内只剩 3，邀请 3
3 {3,4} 组内只剩 4，邀请 4
4 {4,3,2,1} 组内只剩 2，邀请 2

最终被邀请的是 1,3,4,2，答案为 4。
每头牛只会入队一次，每个“牛属于某组”的关系也只会在这头牛出队时被处理一次。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000000 + 5;

int n, m;
vector<vector<int>> groups;
vector<vector<int>> belong;
vector<int> rest_count;
vector<char> invited;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    groups.assign(m + 1, vector<int>());
    belong.assign(n + 1, vector<int>());
    rest_count.assign(m + 1, 0);
    invited.assign(n + 1, 0);

    for (int group_id = 1; group_id <= m; ++group_id) {
        int size;
        cin >> size;
        rest_count[group_id] = size;
        groups[group_id].resize(size);

        for (int i = 0; i < size; ++i) {
            int cow;
            cin >> cow;
            groups[group_id][i] = cow;
            belong[cow].push_back(group_id);
        }
    }

    queue<int> q;
    int ans = 0;

    auto invite_cow = [&](int cow) {
        if (invited[cow]) return;
        invited[cow] = 1;
        q.push(cow);
        ++ans;
    };

    invite_cow(1);
    for (int group_id = 1; group_id <= m; ++group_id) {
        if (rest_count[group_id] == 1) {
            invite_cow(groups[group_id][0]);
        }
    }

    while (!q.empty()) {
        int cow = q.front();
        q.pop();

        for (int group_id : belong[cow]) {
            --rest_count[group_id];
            if (rest_count[group_id] != 1) {
                continue;
            }

            // 这个组已经邀请了 k-1 头牛，找出最后一头没有邀请的牛。
            for (int other : groups[group_id]) {
                if (!invited[other]) {
                    invite_cow(other);
                    break;
                }
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度

设所有组大小之和为 S。

  • 建图需要 O(S)O(S)。
  • 队列传播中，每个“牛属于某组”的关系最多处理一次。
  • 当某组首次变成只剩一头未邀请时，会扫描这个组找到最后一头牛；所有组最多各扫描一次，总计 O(S)O(S)。
  • 总时间复杂度 O(S)O(S)，空间复杂度 O(n+S)O(n+S)。

总结

这题可以看成约束传播。
不要反复全局扫描所有组，而是让“新邀请的牛”主动去更新它所在的组。
当某个组只剩一头未邀请时，它就产生新的传播对象，放入队列继续处理。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

一图流解析