拓扑排序的扩展技巧
重要技巧:利用拓扑排序的过程,上游节点逐渐推送消息;给下游节点的技巧
注意:
这个技巧已经是树型 dp 的内容了,不过即便不会动态规划,本节题也能做。
题目 1 最大食物链计数
上游节点向下游节点推送消息，下游节点收到消息后计数，最后统计下游节点的计数之和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int n, m;
void solve() {
cin >> n >> m;
vector<vector<int>> g(n + 1);
vector<int> indegree(n + 1, 0);
queue<int> que;
vector<int> cnt(n + 1, 0);
int ans = 0;
for (int i = 1; i <= m; i++) {
int uu, vv;
cin >> vv >> uu;
g[uu].push_back(vv);
indegree[vv]++;
}
for (int i = 1; i <= n; i++) {
if (indegree[i] == 0) {
que.push(i);
cnt[i] = 1;
}
}
while (!que.empty()) {
auto u = que.front();
que.pop();
for (auto v : g[u]) {
cnt[v] = mod(cnt[v] + cnt[u]); // 下游节点收到消息后计数
if (--indegree[v] == 0) {
que.push(v);
}
}
}
for (int i = 1; i <= n; i++) {
if (g[i].empty()) {
ans = mod(ans + cnt[i]); // 下游节点的计数之和
}
}
cout << ans << endl;
}
题目 2 喧闹和富有
上游节点向下游节点推送消息，下游节点收到消息后修改自己的答案，最后返回得到的答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
vector<int> loudAndRich(vector<vector<int>> &richer, vector<int> &quiet) {
int n = quiet.size();
vector<vector<int>> g(n);
vector<int> indegree(n, 0);
queue<int> que;
vector<int> ans(n);
for (int i = 0; i < n; i++) {
ans[i] = i; // 答案的初始化
}
for (int i = 0; i < richer.size(); i++) {
int uu = richer[i][0];
int vv = richer[i][1];
g[uu].push_back(vv);
indegree[vv]++;
}
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
que.push(i);
}
}
while (!que.empty()) {
auto u = que.front();
que.pop();
for (auto v : g[u]) {
if (quiet[v] > quiet[u]) {
quiet[v] = quiet[u];
ans[v] = ans[u]; // 上游向下游答案的推送
}
if (--indegree[v] == 0) {
que.push(v);
}
}
}
return ans;
}
题目 3 并行课程 III
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int minimumTime(int n, vector<vector<int>> &relations, vector<int> &time) {
int m = relations.size();
vector<vector<int>> g(n);
vector<int> indegree(n, 0);
queue<int> que;
vector<int> ans(n, 0);
for (int i = 0; i < m; i++) {
int uu = relations[i][0] - 1; // 转化为0-based
int vv = relations[i][1] - 1;
g[uu].push_back(vv);
indegree[vv]++;
}
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
que.push(i);
}
}
while (!que.empty()) {
auto u = que.front();
que.pop();
ans[u] = max(time[u], ans[u]);
for (auto v : g[u]) {
ans[v] = max(ans[v], ans[u]);
if (--indegree[v] == 0) {
ans[v] += time[v];
que.push(v);
}
}
}
int res = 0;
for (int i = 0; i < n; i++) {
res = max(ans[i], res); // res应该为所有节点的最大值，而不是最后一个处理的节点
}
return res;
}
注意：
res应该是所有节点的最大值，而不是最后一个处理的节点。- 最后一个处理的节点不一定是整个图中的最大完成时间节点。这取决于图的拓扑结构，特别是当存在多个无后继的终端节点时。
题目 4 参加会议的最多员工数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
int maximumInvitations(vector<int> &favorite) {
int n = favorite.size();
vector<int> indegree(n);
for (int i = 0; i < n; i++) {
indegree[favorite[i]]++;
}
queue<int> que;
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
que.push(i);
}
}
vector<int> deep(n); // 不包括i在内，i之前的最长链的长度
while (!que.empty()) {
int cur = que.front();
que.pop();
int next = favorite[cur];
deep[next] = max(deep[next], deep[cur] + 1); // 传递信息
if (--indegree[next] == 0) {
que.push(next);
}
}
// 目前图中的点，不在环上的，都删除了！（indegree[i] == 0）
// 可能性1：所有小环（中心个数 == 2），算上中心点+延伸点的总个数
int sumOfSmallRings = 0;
// 可能性2：所有大环（中心个数>2），只算中心点，最大环的中心点个数
int bigRings = 0;
for (int i = 0; i < n; i++) {
if (indegree[i] > 0) {
int ringSize = 1;
indegree[i] = 0;
for (int j = favorite[i]; j != i; j = favorite[j]) {
ringSize++;
indegree[j] = 0;
}
if (ringSize == 2) { // 小环，两点+两点延伸点个数
sumOfSmallRings += 2 + deep[i] + deep[favorite[i]];
} else { // 大环取一个最大值
bigRings = max(bigRings, ringSize);
}
}
}
return max(sumOfSmallRings, bigRings);
}
