把每条推荐规则看成依赖一组前提题的规则节点，维护未满足前提数和前提最大完成天数，单调传播每道题的最早完成日。
OJ: luogu
题目 ID: P8893
难度:普及+/提高
标签:拓扑排序图论思维队列
日期: 2026-06-19 22:45
题意
有一些题在第 0 天就会被推荐。
之后每条规则都形如：如果集合 S 中的题都已经做完，并且其中至少有一道题是“今天刚做的”，那么下一天会推荐目标题 v。
问最早第几天能做完第 K 题；若做不到输出 -1。
思路
状态图
这张图把“题集触发一条规则，再推荐目标题”的关系画出来：
flowchart LR Q1["题 1"] --> R1["规则 A"] Q2["题 2"] --> R1 R1 --> Q3["题 3"] Q1 --> R2["规则 B"] Q2 --> R2 R2 --> Q6["题 6"]
图里的 规则 A / 规则 B 不是题，而是“依赖集合已经全部满足”的条件节点。
当某条规则的所有前提题都完成时，就能在下一天得到它指向的目标题。
先看一个小数据暴力：
#include <bits/stdc++.h>
using namespace std;
struct Rule {
int v;
int need_mask;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k, p;
cin >> n >> k >> p;
int init_mask = 0;
for (int i = 1; i <= p; ++i) {
int x;
cin >> x;
init_mask |= 1 << (x - 1);
}
int r;
cin >> r;
vector<Rule> rules(r);
for (int i = 0; i < r; ++i) {
int v, cnt;
cin >> v >> cnt;
rules[i].v = v;
rules[i].need_mask = 0;
for (int j = 0; j < cnt; ++j) {
int u;
cin >> u;
rules[i].need_mask |= 1 << (u - 1);
}
}
queue<pair<int, int>> q;
map<pair<int, int>, int> dist;
q.push({0, init_mask});
dist[{0, init_mask}] = 0;
while (!q.empty()) {
auto cur = q.front();
q.pop();
int solved = cur.first;
int rec = cur.second;
int day = dist[cur];
int available = rec & (~solved);
for (int take = available;; take = (take - 1) & available) {
int new_solved = solved | take;
if (new_solved & (1 << (k - 1))) {
cout << day << '\n';
return 0;
}
int new_rec = rec;
for (const auto &rule : rules) {
if ((new_solved & rule.need_mask) == rule.need_mask &&
(take & rule.need_mask) != 0) {
new_rec |= 1 << (rule.v - 1);
}
}
pair<int, int> nxt = {new_solved, new_rec};
if (!dist.count(nxt)) {
dist[nxt] = day + 1;
q.push(nxt);
}
if (take == 0) {
break;
}
}
}
cout << -1 << '\n';
return 0;
}暴力做法把状态写成 (已经做完的题集合, 已经被推荐过的题集合)，按天 BFS，并枚举今天做哪些题。它适合小数据对拍，但正式数据显然不能这么做。
这题真正该抓的是“每道题最早在哪一天完成”。
设 day[x] 表示题 x 的最早完成天数。
如果一条规则依赖集合为 S，那么它最早什么时候触发？
- 只有
S中所有题都做完才能触发； - 最早满足这一点的那一天，就是
S里最后完成的那道题完成的那一天； - 也就是
max(day[u])。
并且达到这个最大值的那道题，天然就满足题意里的“今天刚做过一题”。
所以目标题 v 的最早完成天数就是：
max(day[u]) + 1 , u in S
于是整题可以改写成一个单调传播问题：
- 初始推荐题的完成天数都是
0。 - 对每条规则维护：
- 还有多少个前提题没完成；
- 已完成前提题里的最大完成天数。
- 每当一题
u的最早完成天数确定，就去更新所有依赖u的规则。 - 某条规则一旦所有前提齐了，就能推出目标题的最早完成天数。
这和拓扑排序很像，只不过“边”变成了“一个题集指向一条规则，再指向目标题”。
代码
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
int n, k, p, r;
int answer_day[5005];
int need_count[5005], max_need_day[5005], target_question[5005];
vector<int> depend_rules[5005];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k >> p;
for (int i = 1; i <= n; ++i) {
answer_day[i] = INF;
}
queue<int> q;
for (int i = 1; i <= p; ++i) {
int x;
cin >> x;
if (answer_day[x] > 0) {
answer_day[x] = 0;
q.push(x);
}
}
cin >> r;
for (int i = 1; i <= r; ++i) {
int v, cnt;
cin >> v >> cnt;
target_question[i] = v;
need_count[i] = cnt;
max_need_day[i] = -1;
for (int j = 1; j <= cnt; ++j) {
int u;
cin >> u;
depend_rules[u].push_back(i);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int id : depend_rules[u]) {
--need_count[id];
max_need_day[id] = max(max_need_day[id], answer_day[u]);
if (need_count[id] == 0) {
int v = target_question[id];
int cand = max_need_day[id] + 1;
if (cand < answer_day[v]) {
answer_day[v] = cand;
q.push(v);
}
}
}
}
if (answer_day[k] == INF) {
cout << -1 << '\n';
} else {
cout << answer_day[k] << '\n';
}
return 0;
}复杂度
设所有规则依赖集合大小之和为 S，时间复杂度
总结
这题难点在于它不是普通边图，而是“一个目标依赖一组前提”的超边模型。只要把规则单独看成节点，维护前提数量和前提最大完成天数，整个过程就能像拓扑传播一样一次做完。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
