NO.93十六届蓝桥杯备战|图论基础-拓扑排序|有向无环图|AOV网|摄像头|最大食物链计数|杂物(C++)

有向⽆环图

若⼀个有向图中不存在回路，则称为有向⽆环图(directed acycline graph)，简称 DAG 图

AOV⽹

举⼀个现实中的例⼦：课程的学习是有优先次序的，如果规划不当会严重影响学习效果。课程间的先后次序可以⽤有向图表⽰

在这种有向图中，⽤顶点表⽰活动，⽤有向边< v i , v j v_{i}, v_{j} vi​,vj​>表⽰活动 v i v_{i} vi​必须先于活动 v j v_{j} vj​进⾏，这种有向图叫做顶点表⽰活动的⽹络(Activity On Vertex Network)，简称 AOV ⽹

AOV⽹中不能有回路，否则就不能确定回路中的活动究竟哪个先实施。因此⼀个可⾏的AOV⽹必须是有向⽆环图

拓扑排序

拓扑排序的⽬标是将有向⽆环图中的所有结点排序，使得排在前⾯的结点不能依赖于排在后⾯的结点。在课程问题中，相当于就是找到⼀个排课的合法顺序。具体流程可借助队列进⾏：

1. 将图中所有⼊度为0的点，加⼊到队列中；
2. 取出队头元素，删除与该点相连的边。如果删除之后的后继结点的⼊度变为0，加⼊到队列中；
3. 重复2操作，直到图中没有点或者没有⼊度为0的点为⽌。
   拓扑排序判断是否有环：
   跑⼀遍拓扑排序算法，如果有结点没有进队，那么就表明有环

B3644 【模板】拓扑排序 / 家谱树 - 洛谷

#include using namespace std;const int N = 110;int n;vector edges[N];int in[N];int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i > j, j) { edges[i].push_back(j); in[j]++; } } queue q; for (int i = 1; i <= n; i++) { if (in[i] == 0) q.push(i); } while (q.size()) { int x = q.front(); q.pop(); cout << x << \" \"; //删除对应的边 for (auto y : edges[x]) { in[y]--; if (in[y] == 0) q.push(y); } } return 0;}

P2712 摄像头 - 洛谷

拓扑排序判断是否有环。
直接跑⼀遍拓扑排序，然后统计⼀下有多少摄像头没有出队。那么这些没有出队的摄像头就是环⾥⾯的元素。
注意：

• 有些位置可能没有摄像头，需要判断⼀下

#include using namespace std;const int N = 510;int n;vector edges[N];int in[N];bool st[N];int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i > x >> m; st[x] = true; while (m--) { cin >> y; edges[x].push_back(y); in[y]++; } } queue q; //入度为0的点加入队列 for (int i = 0; i <= 500; i++) { if (st[i] && in[i] == 0) q.push(i); } while (q.size()) { auto x = q.front(); q.pop(); for (auto y : edges[x]) { in[y]--; if (st[y] && in[y] == 0) q.push(y); } } int ret = 0; for (int i = 0; i <= 500; i++) { if (st[i] && in[i]) ret++; } if (ret == 0) cout << \"YES\" << endl; else cout << ret << endl; return 0;}

P4017 最大食物链计数 - 洛谷

拓扑排序的过程中，进⾏动态规划。
对于每⼀个节点i，通过它的路径为：前驱所有结点的路径总数之和。因此，可以在拓扑排序的过程中，维护从起点开始到达每⼀个节点的路径总数

#include using namespace std;const int N = 5010, MOD = 80112002;int n, m;vector edges[N];int in[N], out[N];int f[N];int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i > x >> y; edges[x].push_back(y); in[y]++, out[x]++; } queue q; for (int i = 1; i <= n; i++) { if (in[i] == 0) { f[i] = 1; q.push(i); } } while (q.size()) { auto x = q.front(); q.pop(); for (auto y : edges[x]) { f[y] = (f[y] + f[x]) % MOD; in[y]--; if (in[y] == 0) q.push(y); } } int ret = 0; for (int i = 1; i <= n; i++) { if (out[i] == 0) { ret = (ret + f[i]) % MOD; } } cout << ret << endl; return 0;}

P1113 杂务 - 洛谷

拓扑排序的过程中，进⾏动态规划。
对于每⼀个事件i，完成它的最⼩时间为：完成前驱所有事件的最⼩时间中的最⼤值+当前事件的完成时间。因此，可以在拓扑排序的过程中，维护每⼀个事件完成的最⼩时间，然后更新当前事件的最⼩时间

#include using namespace std;const int N = 10010;int n;vector edges[N];int in[N], f[N];int len[N];int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i > b >> len[b]; while (cin >> a, a) { edges[a].push_back(b); in[b]++; } } queue q; for (int i = 1; i <= n; i++) { if (in[i] == 0) q.push(i); } int ret = 0; while (q.size()) { int a = q.front(); q.pop(); f[a] += len[a]; ret = max(ret, f[a]); for (auto b : edges[a]) { f[b] = max(f[b], f[a]); in[b]--; if (in[b] == 0) q.push(b); } } cout << ret << endl; return 0;}