复兴提高班第十八课 拓扑排序
2025-10-18 20:32:12
发布于：上海
9阅读
0回复
0点赞
T1【拓扑排序】摄像头
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e2 + 9;
bool vis[maxn];
int deg[maxn];
vector<int> ve[maxn];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x, m;
cin >> x >> m;
while (m--) {
int y;
cin >> y;
ve[x].push_back(y);
deg[y]++;
}
}
queue<int> q;
for (int i = 1; i <= n; i++) {
if (deg[i] == 0) {
vis[i] = 1;
q.push(i);
}
}
while (q.size()) {
int r = q.front();
q.pop();
for (int i = 0; i < ve[r].size(); i++) {
int y = ve[r][i];
if (--deg[y] == 0) {
q.push(y);
vis[y] = 1;
}
}
}
int num = 0;
for (int i = 1; i <= n; i++) {
if (!vis[i]) num++;
}
if (num) cout << num;
else cout << "YES";
return 0;
}
T2【拓扑排序】判环
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 9;
vector<int> ve[maxn];
int deg[maxn];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
ve[u].push_back(v);
deg[v]++;
}
priority_queue<int, vector<int>, greater<int> >q;
for (int i = 1; i <= n; i++) {
if (deg[i] == 0) q.push(i);
}
vector<int> ans;
while (q.size()) {
int r = q.top();
q.pop();
ans.push_back(r);
for (int i = 0; i < ve[r].size(); i++) {
int y = ve[r][i];
if (--deg[y] == 0)q.push(y);
}
}
if (ans.size() != n) cout << "has circle";
else {
for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
}
return 0;
}
T3【拓扑排序】杂务
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 9;
int dp[maxn];
vector<int> ve[maxn];
int deg[maxn], times[maxn];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> times[i];
int k;
cin >> k;
while (k--) {
int a;
cin >> a;
ve[a].push_back(i);
deg[i]++;
}
}
queue<int> q;
for (int i = 1; i <= n; i++) {
if (deg[i] == 0) {
q.push(i);
dp[i] = times[i];
}
}
while (q.size()) {
int r = q.front();
q.pop();
for (int i = 0; i < ve[r].size(); i++) {
int y = ve[r][i];
dp[y] = max(dp[y], dp[r] + times[y]);
if (--deg[y] == 0) q.push(y);
}
}
int ans = 0;
for (int i = 1; i <= n; i++) ans = max(ans, dp[i]);
cout << ans;
return 0;
}
T4【拓扑排序】最大食物链计数
#include<bits/stdc++.h>
using namespace std;
const int MOD = 80112002;
const int maxn = 2e3 + 9;
int dp[maxn];
vector<int> ve[maxn];
int deg[maxn];
bool vis[maxn];
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int A, B;
cin >> A >> B;
ve[A].push_back(B);
deg[B]++;
vis[A] = 1;
}
queue<int> q;
for (int i = 1; i <= n; i++) {
if (deg[i] == 0) {
dp[i] = 1;
q.push(i);
}
}
while (q.size()) {
int r = q.front();
q.pop();
for (int i = 0; i < ve[r].size(); i++) {
int y = ve[r][i];
dp[y] += dp[r];
dp[y] %= MOD;
if (--deg[y] == 0) q.push(y);
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
ans += dp[i];
ans %= MOD;
}
}
cout << ans;
return 0;
}
T5【拓扑排序】时间线
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 9;
int S[maxn], deg[maxn];
struct node {
int v, w;
};
vector<node> ve[maxn];
int dp[maxn];
int main() {
int N, M, C;
cin >> N >> M >> C;
for (int i = 1; i <= N; i++) cin >> S[i];
for (int i = 0; i < C; i++) {
int a, b, x;
cin >> a >> b >> x;
ve[a].push_back({ b,x });
deg[b]++;
}
queue<int> q;
for (int i = 1; i <= N; i++) {
dp[i] = S[i];
if (deg[i] == 0) q.push(i);
}
while (q.size()) {
int r = q.front();
q.pop();
for (int i = 0; i < ve[r].size(); i++) {
int y = ve[r][i].v, w = ve[r][i].w;
dp[y] = max(dp[y], dp[r] + w);
if (--deg[y] == 0) q.push(y);
}
}
for (int i = 1; i <= N; i++) cout << dp[i] << '\n';
return 0;
}
这里空空如也
有帮助，赞一个