碎碎念
- 本来说好的练习动态规划，哎。。。。
题目
题目原文请移步下面的链接
- https://www.luogu.com.cn/problem/P4017
- 参考题解：https://www.luogu.com.cn/problem/solution/P4017
- 标签：
OI、拓扑排序
题目背景
你知道食物链吗？Delia 生物考试的时候，数食物链条数的题目全都错了，因为她总是重复数了几条或漏掉了几条。于是她来就来求助你，然而你也不会啊！写一个程序来帮帮她吧。
题目描述
给你一个食物网，你要求出这个食物网中最大食物链的数量。
（这里的“最大食物链”，指的是生物学意义上的食物链，即最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。）
Delia 非常急，所以你只有 11 秒的时间。
由于这个结果可能过大，你只需要输出总数模上 80112002 的结果。
输入格式
第一行，两个正整数 n、m，表示生物种类 n 和吃与被吃的关系数 m。
接下来 m 行，每行两个正整数，表示被吃的生物A和吃A的生物B。
输出格式
一行一个整数，为最大食物链数量模上 80112002 的结果。
输入输出样例
输入 #1
代码语言：javascript复制5 7
1 2
1 3
2 3
3 5
2 5
4 5
3 4
输出 #1
代码语言：javascript复制5
题解
- 一道拓扑排序
- 其实是比较板子了，但我华丽丽的踩了坑，首先，这个东西他根本不能用优先队列
所以当初为什么我另一题优先队列AC了，这是挂分的第一个原因 - 另一个是你算方案数累计的时候肯定是现有的加上继承来的，所以他并不是 1
我承认我太愚蠢了
AC代码
代码语言：javascript复制#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <stack>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
#define endl 'n';
struct edge {
int in_degree, out_degree;
};
bool cmp (edge x, edge y){
return x.in_degree <= y.in_degree;
};
const int mod = 80112002;
void best_coder() {
int n, m;
cin >> n >> m;
vector<vector<int>> g(n 1);
vector<edge> v(n 1);
for (int i = 0; i < m; i) {
int a, b;
cin >> a >> b;
g[b].push_back(a);
v[b].out_degree;
v[a].in_degree;
}
queue<int> q;
vector<int> ans(n 1);
for (int i = 1; i <= n; i) {
if (v[i].in_degree == 0) {
q.push(i);
ans[i] = 1;
}
}
while (!q.empty()) {
int k = q.front();
q.pop();
for (auto i : g[k]) {
--v[i].in_degree;
ans[i] = (ans[k] ans[i]) % mod;
if (v[i].in_degree == 0) {
q.push(i);
}
}
}
long long cnt = 0;
for (int i = 1; i <= n; i) {
if (v[i].out_degree == 0) {
cnt = (cnt ans[i]) % mod;
}
}
cout << cnt;
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
// 返回
return 0;
}
