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

有向⽆环图

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

AOV⽹

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

在这种有向图中，⽤顶点表⽰活动，⽤有向边<$v_i,v_j$>表⽰活动$v_i$必须先于活动$v_j$进⾏，这种有向图叫做顶点表⽰活动的⽹络(Activity On Vertex Network)，简称 AOV ⽹

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

拓扑排序

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

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

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

#include <bits/stdc++.h>
using namespace std;const int N = 110;int n;
vector<int> edges[N];
int in[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; i++){int j;while (cin >> j, j){edges[i].push_back(j);in[j]++;}}queue<int> 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 <bits/stdc++.h>
using namespace std;const int N = 510;int n;
vector<int> 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 <= n; i++){int x, m, y; cin >> x >> m;st[x] = true;while (m--){cin >> y;edges[x].push_back(y);in[y]++;}}queue<int> 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 <bits/stdc++.h>
using namespace std;const int N = 5010, MOD = 80112002;int n, m;
vector<int> 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 <= m; i++){int x, y; cin >> x >> y;edges[x].push_back(y);in[y]++, out[x]++;}queue<int> 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 <bits/stdc++.h>
using namespace std;const int N = 10010;int n;
vector<int> 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 <= n; i++){int b,a;cin >> b >> len[b];while (cin >> a, a){edges[a].push_back(b);in[b]++;}}queue<int> 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;
}