【洛谷 P4017】最大食物链计数 题解(深度优先搜索+动态规划+邻接表+记忆化搜索+剪枝)

最大食物链计数

题目背景

你知道食物链吗?Delia 生物考试的时候,数食物链条数的题目全都错了,因为她总是重复数了几条或漏掉了几条。于是她来就来求助你,然而你也不会啊!写一个程序来帮帮她吧。

题目描述

给你一个食物网,你要求出这个食物网中最大食物链的数量。

(这里的“最大食物链”,指的是生物学意义上的食物链,即最左端是不会捕食其他生物的生产者,最右端是不会被其他生物捕食的消费者。)

Delia 非常急,所以你只有 1 1 1 秒的时间。

由于这个结果可能过大,你只需要输出总数模上 80112002 80112002 80112002 的结果。

输入格式

第一行,两个正整数 n 、 m n、m nm,表示生物种类 n n n 和吃与被吃的关系数 m m m

接下来 m m m 行,每行两个正整数,表示被吃的生物A和吃A的生物B。

输出格式

一行一个整数,为最大食物链数量模上 80112002 80112002 80112002 的结果。

样例 #1

样例输入 #1

5 7
1 2
1 3
2 3
3 5
2 5
4 5
3 4

样例输出 #1

5

提示

各测试点满足以下约定:

【补充说明】

数据中不会出现环,满足生物学的要求。(感谢 @AKEE )


思路

食物网可以看作是一个有向图,每个生物种类是一个节点,每个食物关系是一个有向边。所求的最大食物链的数量,就是计算有向图中从源点(没有入度的点)到达终点(没有出度的点)的所有路径的数量。

首先,定义一些全局变量。其中,N 是节点的最大数量,MOD 是取模的基数,nm 分别表示节点的数量和边的数量,ans 用来存储最终的结果,dp 是一个数组,用来存储每个节点的最大食物链的数量,inDoutD 是两个数组,分别用来存储每个节点的入度和出度,g 是一个邻接表,用来存储图的信息,vis 是一个位集,用来标记每个节点是否被访问过。

main 函数中,首先通过 memset 函数将 inDoutDdp 数组的所有元素初始化为 0,然后读取节点的数量 n 和边的数量 m,并根据输入的边的信息,更新 inDoutDg。之后,对于每一个没有入度的节点,调用 dfs 函数进行深度优先搜索,并更新 ans

dfs 函数中,首先检查当前节点是否被访问过,如果已经被访问过,就直接返回。然后,将当前节点标记为已访问。接着,如果当前节点没有出度,就将 dp 数组中对应的元素设置为 1,然后返回。否则,对于当前节点的每一个邻接节点,调用 dfs 函数,并更新 dp 数组中对应的元素。

最后,输出 ansMOD 取模的结果。

注意

由于结果可能过大,每次计算路径数求和时都需要输出总数模上 80112002 80112002 80112002 的结果,否则无法通过部分测试点。


AC代码

#include <algorithm>
#include <bitset>
#include <cstring>
#include <iostream>
#include <vector>
#define AUTHOR "HEX9CF"
using namespace std;
using ll = long long;

const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f;
const int MOD = 80112002;

ll n, m;
ll ans = 0;
ll dp[N];
ll inD[N], outD[N];
vector<ll> g[N];
bitset<N> vis;

void dfs(ll x) {
	if (vis[x]) {
		return;
	}
	vis[x] = 1;
	// cout << x << endl;
	if (!outD[x]) {
		// 最右端是不会被其他生物捕食的消费者
		dp[x] = 1;
		return;
	}
	ll sum = 0;
	for (const auto i : g[x]) {
		dfs(i);
		sum += dp[i];
		sum %= MOD;
	}
	dp[x] = max(dp[x], sum);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	memset(inD, 0, sizeof(inD));
	memset(outD, 0, sizeof(outD));
	memset(dp, 0, sizeof(dp));

	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		ll a, b;
		cin >> a >> b;
		outD[a]++;
		inD[b]++;
		g[a].push_back(b);
	}

	vis.reset();
	for (int i = 1; i <= n; i++) {
		if (!inD[i]) {
			// 最左端是不会捕食其他生物的生产者
			dfs(i);
			ans += dp[i];
			ans %= MOD;
			// cout << i << " " << dp[i] << endl;
		}
	}
	//	for(int i = 1; i <= n; i++) {
	//		cout << i << " " << dp[i] << endl;
	//	}
	cout << (ans % MOD) << "\n";
	return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/547407.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【CSS面试题】Flex实现九宫格

考察知识&#xff1a; flex布局 水平垂直居中的实现 初始效果 代码关键&#xff1a;给父盒子添加以下属性 flex-wrap: wrap; /* 允许换行 */justify-content: space-around; /* 主轴对齐方式 */align-content: space-around; /* 多行在侧轴上的对齐方式 */<!DOCTYPE html&…

如何让Nrf connect、EFR connect直接显示特征值数据及其单位

效果如图&#xff1a;app直接显示了我的温度&#xff0c;并且有两位小数&#xff0c;还有温度单位。这是怎么做到的呢&#xff1f; 这次我们仍以TLS8258为例&#xff0c;当然如果是其他蓝牙芯片&#xff0c;配置方式也是大差不差&#xff0c;规则一样的。 #define GATT_CHARA…

租用马来西亚服务器:稳定高效的网络选择

马来西亚首都是吉隆坡。作为一个新兴的多元化经济国家&#xff0c;也属于亚洲四小龙之一。地理位置优越&#xff0c;中间隔着南中国海。一部分是北接泰国的位于马来半岛的西马来西亚&#xff0c;另一部分则是东马来西亚&#xff0c;在婆罗洲岛的北部。这种地理位置有利于促进该…

[Java EE] 计算机工作原理与操作系统简明概要

1. 计算机工作原理 1.1 生活中常见的计算机 计算机分为通用计算机和专用计算机,计算机并不单单指的是电脑,还有我们平时使用的手机,ipad,智能手表等终端设备都是计算机.还有我们用户不常见的计算机,比如服务器. 还有许多嵌入式设备(针对特定场景定制的"专用计算机"…

系统学c#:1、基础准备(软件下载与安装)

一、Vs软件下载与安装 访问Visual Studio官方网站&#xff1a; https://visualstudio.microsoft.com/zh-hans/downloads 下载Visual Studio 运行exe文件&#xff0c;点击“继续” 初始文件安装完成后选择我们需要安装的项&#xff0c;并勾选好必要的单个组件&#xff0c;设…

cookie与session及其区别

一、cookie 1. 为什么需要cookie&#xff1f; web程序使用HTTP协议进行传输&#xff0c;而HTTP协议是无状态的协议&#xff08;即对事务处理无记忆性&#xff0c;如果后续处理需要使用前面的信息&#xff0c;只能重传&#xff0c;导致每次连接传送的数据量增大&#xff09;。c…

maven3.9+下载安装

maven介绍 Maven 是一个项目管理和理解工具&#xff0c;它基于项目对象模型&#xff08;POM&#xff09;概念。Maven 可以帮助开发者定义项目结构、依赖关系、构建过程以及其他任务。它主要用于 Java 项目&#xff0c;但也可以用于其他类型的项目。Maven 的主要目标是简化构建…

单元测试四大过程

单元测试四大过程&#xff08;蓝桥课学习笔记&#xff09; 单元测试过程 单元测试是软件测试过程中的一个关键环节&#xff0c;它与集成测试、系统测试一样&#xff0c;分为测试策划、测试设计、测试执行和测试总结几个阶段。 单元测试过程中每个阶段需要完成的主要工作如下&…

【Linux】磁盘管理和文件系统

目录 一、硬盘 1.硬盘结构 2.结构类型 二、MBR与磁盘分区 1.MBR主引导记录 2.磁盘分区结构 三、文件系统类型 四、linux系统添加并使用新硬盘的步骤 1.添加新的硬盘 2.刷新识别 3.进行分区 4.格式化&#xff0c;创建文件系统 5.挂载使用 一、硬盘 1.硬盘结构…

Linux程序调试优化(1)——内存占用详解及优化思路

文章目录 1.free查看总体的内存占用2./proc/$PID/status 查看某进程状态 linux开发最重要的两个参数&#xff0c;分别是内存以及CPU使用率&#xff0c;若内存出现严重不足&#xff0c;则在需要使用内存时&#xff0c;可能出现申请不到的情况&#xff0c;导致 OOM&#xff0c;L…

顺丰快递免费的API开放物流信息查询接口

文章目录 目录 文章目录 安装流程 小结 概要安装流程技术细节小结 概要 官方地址&#xff1a;顺丰开放平台 注册成功之后&#xff0c;需要认证&#xff0c;进入当前如图下&#xff0c;认证的入口如图&#xff08;已认证的页面&#xff09; 点击新建应用 安装流程 1. 需要下载…

【模拟】Leetcode 替换所有的问号

题目讲解 1576. 替换所有的问号 算法讲解 这里有两个特殊情况&#xff1a;如果&#xff1f;在第一个位置&#xff0c;只需要判断后面的符号&#xff1b; 如果&#xff1f;在最后一个位置&#xff0c;只需要判断前面的符号 class Solution { public:string modifyString(stri…

Java:定时任务无法正常执行(scheduling + ShedLock)

目录 一、场景二、代码片段三、排查四、原因五、解决 一、场景 1、使用定时任务(scheduling) 分布式锁(ShedLock)定期执行一段代码 2、configureTasks()对于任务执行周期的更新是正常的 3、但任务方法无法被执行 二、代码片段 三、排查 1、确认Trigger没有问题 2、查看red…

如何在MobaXterm上使用rz命令

1、首先输入命令和想下载的文件&#xff0c;如下图&#xff1a; 2、按住ctrl鼠标右键&#xff0c;选择如下选项&#xff1a; 上传命令是rz&#xff0c;选择Receive...... 下载命令是sz&#xff0c;选择Send...... 3、我这里是要把Linux上的文件下载到我的本地window磁盘&…

【计算机考研】408网课汇总+资源分享

408王道的视频就比较通俗易懂 王道的教材非常契合408的大纲&#xff0c;是专门为408大纲而编写的&#xff0c;而教材是方方面面都讲解的透彻。 建议王道为主&#xff0c;网络搜索为辅&#xff01; 王道中讲解不清楚&#xff0c;看不懂的知识点&#xff0c;可以尝试在网络上进…

小车项目介绍

STM32智能小车基于STM32F103C8T6进行开发 该项目具有OLED,USART串口,ADC测量电压,陀螺仪,超声波测距模块,红外循迹模块,蓝牙模块,按键,电机驱动,电机,舵机,电源等功能 功能详细介绍: OLED模块 使用:OLED显示屏模块 0.96寸 IIC/SPI 选择原因&#xff1a;价格较低、使用方便…

OpenHarmony轻量系统开发【4】编写第一个程序、启动流程分析

摘要&#xff1a;本文简单介绍如何编写第一个hello world程序&#xff0c;以及程序是被执行的 适合群体&#xff1a;适用于Hi3861开发板&#xff0c;启动流程分析 4.1编写第一个程序 编写一个hello world程序比较简单&#xff0c;可以参考官网&#xff1a; https://gitee.c…

Redis中的订阅发布(三)

订阅发布 发送消息 当一个Redis客户端执行PUBLISH 命令将消息message发送给频道channel的时候&#xff0c;服务器需要执行以下 两个动作: 1.将消息message发送给channel频道的所有订阅者2.如果一个或多个模式pattern与频道channel相匹配&#xff0c;那么将消息message发送给…

开源相机管理库Aravis例程学习(二)——连续采集multiple-acquisition-main-thread

开源相机管理库Aravis例程学习&#xff08;二&#xff09;——连续采集multiple-acquisition-main-thread 简介例程代码函数说明arv_camera_set_acquisition_modearv_camera_create_streamarv_camera_get_payloadarv_buffer_newarv_stream_push_bufferarv_camera_start_acquisi…

CCleaner怎么清理软件缓存 CCleaner清理要勾选哪些 ccleanerfree下载

CCleaner软件是一款优秀的数据清理软件&#xff0c;其中没有硬盘和内存的设置&#xff0c;也不含任何广告软件&#xff0c;其出色的注册表清洁功能能够保证您的电脑更稳定运行。本文将围绕CCleaner怎么清理软件缓存&#xff0c;CCleaner清理要勾选哪些的相关内容进行介绍。 一、…