在网上建设网站需要花钱么,营销型网站怎么做,淘宝怎么下载视频,电子设计网站上链接#xff1a;P4017 最大食物链计数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P4017
上题干#xff1a; 题目背景 你知道食物链吗#xff1f;Delia 生物考试的时候#xff0c;数食物链条数的题目全都错了#xff0c;因为她总是…上链接P4017 最大食物链计数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P4017
上题干 题目背景 你知道食物链吗Delia 生物考试的时候数食物链条数的题目全都错了因为她总是重复数了几条或漏掉了几条。于是她来就来求助你然而你也不会啊写一个程序来帮帮她吧。 题目描述 给你一个食物网你要求出这个食物网中最大食物链的数量。 这里的“最大食物链”指的是生物学意义上的食物链即最左端是不会捕食其他生物的生产者最右端是不会被其他生物捕食的消费者。 Delia 非常急所以你只有 11 秒的时间。 由于这个结果可能过大你只需要输出总数模上 8011200280112002 的结果。 输入格式 第一行两个正整数 n、m表示生物种类 n 和吃与被吃的关系数 m。 接下来 m 行每行两个正整数表示被吃的生物A和吃A的生物B。 输出格式 一行一个整数为最大食物链数量模上 80112002 的结果。 输入输出样例 输入 #1复制 5 7
1 2
1 3
2 3
3 5
2 5
4 5
3 4 输出 #1复制 5 说明/提示 各测试点满足以下约定 【补充说明】 数据中不会出现环满足生物学的要求。 数据大小:M5e57N5e37 取模mod80112002
一个vector 用来储存点的关系
一个数组f来储存答案。
一个数组outd表示入度
一个数组ind表示出度。
一个队列q每次用来增加新的入度为0的点和删除已经用过的入度为0的点。 开始分析
我们要求所有的完整食物链的个数也就是求所有起点是生产者终点是最高级的消费者。 我们可以得到这样的图 假设数组f【i】表示以生产者为起点到i号生物的路径数量。
由此我们可以得到递推关系。
f【5】 f【2】f【3】f【4】
f【2】f【1】
f【3】f【2】f【1】
f【4】f【3】
f【1】1
这就是这样例的结果。f【5】1225 先将所有入度为0的数字的f【】初始化为1其他的初始化为0
1对其他能吃它的贡献为f【1】现在我们将1删除然后将1的捕食关系删除也就是能吃1的入度-1然后给它们加上f【1】也就是f【2】f【1】f【3】f【1】
现在场上剩下的图像就是 继续找入度为0的点现在是2那么删去2给能吃2的加上2的贡献
f【3】f【1】f【2】
f【5】f【2】
然后删除后的图像就是这样 继续找图中入度为0的点3
删除3的痕迹给能吃3的加上3的贡献
f【5】f【2】f【3】
f【4】f【3】
最后删除4以及4 的痕迹给能吃4的加上4的贡献
f【5】f【2】f【3】f【4】5
此时剩下的一定是最高消费者那么其代表的数值就一定是答案。
上代码 const int mod 80112002;
const int M 5e57;
const int N 5e3 7;
queueint q;
int outd[N];
int ind[N];
int f[N];
int ans;
vectorint p[N];
int main()
{int n, m;cin n m;for (int i 0; i m; i){int a, b;cin a b;p[b].push_back(a);outd[b];ind[a];}for (int i 1; i n; i){if (ind[i] 0) {q.push(i);f[i] 1;}}while (!q.empty()) {int x q.front();q.pop();for (int i 0; i p[x].size(); i){f[p[x][i]] f[x];f[p[x][i]] % mod;ind[p[x][i]]--;if (ind[p[x][i]] 0)q.push(p[x][i]);}}for (int i 1; i n; i){if (outd[i] 0)ans (ansf[i])%mod;}cout ans;
}
