当前位置: 首页 > news >正文

《洛谷深入浅出基础篇》P4017最大食物链————拓扑排序

上链接:P4017 最大食物链计数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)icon-default.png?t=N7T8https://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

说明/提示

各测试点满足以下约定:

【补充说明】

数据中不会出现环,满足生物学的要求。

数据大小:M=5e5+7,N=5e3+7

 取模:mod=80112002

一个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】=1+2+2=5

先将所有入度为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 = 5e5+7;
const int N = 5e3 + 7;
queue<int > q;
int outd[N];
int ind[N];
int f[N];
int ans;
vector<int > 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 = (ans+f[i])%mod;}cout << ans;
}

相关文章:

《洛谷深入浅出基础篇》P4017最大食物链————拓扑排序

上链接&#xff1a;P4017 最大食物链计数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P4017 上题干&#xff1a; 题目背景 你知道食物链吗&#xff1f;Delia 生物考试的时候&#xff0c;数食物链条数的题目全都错了&#xff0c;因为她总是…...

设置定时自动请求测试_自动定时循环发送http_post请求---postman工作笔记001

其实就是创建接口文件夹的时候,有个monitor collection 用来监听接口执行情况,这里就可以设置 可以看到多久执行一次对吧,这里可以设置每几分钟执行一次,一共执行多少次等等 但是这里要说明一下,如果需要使用monitor功能,必须需要登录, 所以如果这里点击monitor collection…...

Vue3封装全局插件

定义一个全局加载组件 一、首先定义dom元素 定义一个index.vue文件 <template><div class"loading">loading...</div> </template> <script setup lang"ts"></script> <style scoped> .loading {display: fl…...

【Python 训练营】N_6 求素数

题目 判断101-200之间有多少个素数&#xff0c;并输出所有素数。 分析 判断素数的方法&#xff1a;用一个数分别去除2到sqrt(这个数)&#xff0c;如果能被整除&#xff0c;则表明此数不是素数&#xff0c;反之是素数。 答案 h 0 leap 1 from math import sqrt from sys …...

【图论】关键路径求法c++

代码结构如下图&#xff1a; 其中topologicalSort(float**, int, int*, bool*, int, int)用来递归求解拓扑排序&#xff0c;topologicalSort(float**, int*&, int, int, int)传参图的邻接矩阵mat与结点个数n&#xff0c;与一个引用变量数组topo&#xff0c;返回一个布尔值…...

基于51单片机电子钟万年历LCD1602显示

51单片机的电子钟万年历LCD1602显示 &#x1f534; &#x1f535;51单片机的电子钟万年历LCD1602显示&#x1f534; &#x1f535;主要功能&#xff1a;&#x1f534; &#x1f535;讲解视频&#x1f534; &#x1f535;仿真图&#xff1a;&#x1f534; &#x1f535;程序&…...

时间复杂度和运算

时间复杂度 在算法和数据结构中&#xff0c;有许多时间复杂度比 O(1) 更差的情况。以下是一些常见的时间复杂度&#xff0c;按照从最优到最差的顺序排列&#xff1a; O(1)&#xff1a; 常数时间复杂度&#xff0c;操作的运行时间与输入规模无关&#xff0c;是最理想的情况。 O…...

深入Tailwind CSS中的文本样式

深入Tailwind CSS中的文本样式 样式文本是网页设计的一个基本组成部分&#xff0c;而 Tailwind CSS 提供了范围广泛的实用类&#xff0c;使文本样式设计既高效又有效。 在本本中&#xff0c;我们将探索文本样式的常见最佳实践,讨论潜在的陷阱&#xff0c;并推荐设计方法。我们…...

系统优化软件Bitsum Process Lasso Pro v12.4,供大家学习研究参考

1、自动或手动调整进程优先级;将不需要抑制的进程添加到排除列表; 2、设置动态提升前台运行的进程/线程的优先级 3、设置进程黑名单,禁止无用进程(机制为启动即结束,而非拦截其启动)。 4、优化I/O优先级以及电源模式自动化。 5、ProBalance功能。翻译成中文是“进程平衡…...

敏捷DevOps专家王立杰:端到端DevOps持续交付的5P法则 | IDCF

今天有一个流行的英文缩写词用来刻画这个风云变幻的时代&#xff1a;VUCA&#xff08;乌卡时代&#xff09;。四个英文字母分别表示动荡性&#xff08;Volatility&#xff09;、不确定性&#xff08;Uncertainty&#xff09;、复杂性&#xff08;Complexity&#xff09;和模糊性…...

分布式锁详解

文章目录 分布式锁1. [传统锁回顾](https://blog.csdn.net/qq_45525848/article/details/134608044?csdn_share_tail%7B%22type%22:%22blog%22,%22rType%22:%22article%22,%22rId%22:%22134608044%22,%22source%22:%22qq_45525848%22%7D)1.1. 从减库存聊起1.2. 环境准备1.3. 简…...

Python入门学习篇(二)——算术运算符

1 算术运算符 1.1 分类 类型含义示例注意事项加号12➡3“12”“3"➡"123”数值之间,是加法运算(True为1,False为0)字符串之间,是进行拼接数值和字符串之间是不可以使用加法运算的,会报错-减号1-2➡-1*乘号2*3➡6/除法2/1➡2.0除法的结果永远为小数%取余10%2➡0//取…...

微软发布最新.NET 8长期支持版本,云计算、AI应用支持再强化

11 月 15 日开始的为期三天的 .NET Conf 在线活动的开幕日上&#xff0c;.NET 8作为微软的开源跨平台开发平台正式发布。.NET 团队着重强调云、性能、全栈 Blazor、AI 和 .NET MAUI 是.NET 8的主要亮点。.NET团队在 .NET Conf 2023 [1]活动开幕式上表示&#xff1a;“通过这个版…...

达索系统3DEXPERIENCE WORKS 2024 Fabrication新功能

当发现产品的制造环节&#xff0c;以及因产品模型本身的设计而导致制造环节存在不合理性&#xff0c;从而导致加工制造成本增加。 快速判断&#xff0c;轻松协作 在达索系统3DEXPERIENCE WORKS 2024中我们可以快速的判断产品的可制造性&#xff0c;以及快速与前端设计沟通协作…...

Web3与Web3.0: Web3指的是去中心化和基于区块链的网络,Web3.0指的是链接或语义网络。

目录 Web3与Web3.0: Web3指的是去中心化和基于区块链的网络 Web3.0指的是链接或语义网络。...

98、Text2Room: Extracting Textured 3D Meshes from 2D Text-to-Image Models

简介 github 利用预训练的2D文本到图像模型来合成来自不同姿势的一系列图像。为了将这些输出提升为一致的3D场景表示&#xff0c;将单目深度估计与文本条件下的绘画模型结合起来&#xff0c;提出了一个连续的对齐策略&#xff0c;迭代地融合场景帧与现有的几何形状&#xff0…...

MySQL 优化器 Index Condition Pushdown下推(ICP)

ICP 测试 准备数据 CREATE TABLE icp (employee_id int(6) NOT NULL AUTO_INCREMENT,first_name varchar(20) DEFAULT NULL,last_name varchar(25) DEFAULT NULL,email varchar(25) DEFAULT NULL,phone_number varchar(20) DEFAULT NULL,PRIMARY KEY (employee_id) );insert i…...

ruoyi 若依框架采用第三方登录

在项目中&#xff0c;前后端分离的若依项目&#xff0c;需要通过统一认证&#xff0c;或者是第三方协带认证信息跳转到本系统的指定页面。需要前后端都做相应的改造&#xff0c;由于第一次实现时已过了很久&#xff0c;再次重写时&#xff0c;发现还是搞了很长时间&#xff0c;…...

dom api

dom的全称为Document Object Model,即文档对象模型.所谓文档就是html页面,对象就是js里的对象,通过这个模型把页面上的元素和js里的对象关联起来. 下面是关于dom api的一些常用方法 1.获取元素 使用querySelector()方法获取一个元素 使用querySelectorAll()方法获取所有元素 当…...

音视频项目—基于FFmpeg和SDL的音视频播放器解析(二十一)

介绍 在本系列&#xff0c;我打算花大篇幅讲解我的 gitee 项目音视频播放器&#xff0c;在这个项目&#xff0c;您可以学到音视频解封装&#xff0c;解码&#xff0c;SDL渲染相关的知识。您对源代码感兴趣的话&#xff0c;请查看基于FFmpeg和SDL的音视频播放器 如果您不理解本…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

智能职业发展系统:AI驱动的职业规划平台技术解析

智能职业发展系统&#xff1a;AI驱动的职业规划平台技术解析 引言&#xff1a;数字时代的职业革命 在当今瞬息万变的就业市场中&#xff0c;传统的职业规划方法已无法满足个人和企业的需求。据统计&#xff0c;全球每年有超过2亿人面临职业转型困境&#xff0c;而企业也因此遭…...

TJCTF 2025

还以为是天津的。这个比较容易&#xff0c;虽然绕了点弯&#xff0c;可还是把CP AK了&#xff0c;不过我会的别人也会&#xff0c;还是没啥名次。记录一下吧。 Crypto bacon-bits with open(flag.txt) as f: flag f.read().strip() with open(text.txt) as t: text t.read…...

CTF show 数学不及格

拿到题目先查一下壳&#xff0c;看一下信息 发现是一个ELF文件&#xff0c;64位的 ​ 用IDA Pro 64 打开这个文件 ​ 然后点击F5进行伪代码转换 可以看到有五个if判断&#xff0c;第一个argc ! 5这个判断并没有起太大作用&#xff0c;主要是下面四个if判断 ​ 根据题目…...

从零手写Java版本的LSM Tree (一):LSM Tree 概述

&#x1f525; 推荐一个高质量的Java LSM Tree开源项目&#xff01; https://github.com/brianxiadong/java-lsm-tree java-lsm-tree 是一个从零实现的Log-Structured Merge Tree&#xff0c;专为高并发写入场景设计。 核心亮点&#xff1a; ⚡ 极致性能&#xff1a;写入速度超…...

深度解析云存储:概念、架构与应用实践

在数据爆炸式增长的时代&#xff0c;传统本地存储因容量限制、管理复杂等问题&#xff0c;已难以满足企业和个人的需求。云存储凭借灵活扩展、便捷访问等特性&#xff0c;成为数据存储领域的主流解决方案。从个人照片备份到企业核心数据管理&#xff0c;云存储正重塑数据存储与…...