【备战蓝桥杯】快来学吧~ 图论巩固,Delia的生物考试

发布时间:2024年01月20日

蓝桥杯备赛 | 洛谷做题打卡day12

  • 最大食物链计数

    题目背景

    你知道食物链吗?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
    

    提示

    各测试点满足以下约定:

    【补充说明】

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

题解代码

学会利用新知,自己多试试并尝试积攒一些固定解答方案,debug,以下是题解代码 ~

总的思路:拓扑排序

这里具体讲一下为什么要用拓扑排序(思维过程):

1、这是一道图论题;

2、不是求最短路;

3、根据提示“最左端是不会捕食其他生物的生产者”可以想到,我们要入度为零的点开始查找;

4、再看一遍题目,就是求路径数,当且仅当一个点的入度变为零时才需要入队,并不是数据更新一次就要入队;

5、出度为零的点的路径总数和就是答案。

思路已经呼之欲出了:拓扑排序!


下面讲讲如何实现。

拓扑排序的精髓就在于每个点只会入队一次,每条边只会通过一次,所以时间复杂度就有很好的保证O(N+M),SPFA的玄学时间复杂度)。

正确性说明:题目的补充说明告诉我们这是一张DAG(有向无环图),因此必定存在一个入度为0的点,也因此每一个点都会被遍历。

当一个点的入度变为零,即所有它能吃的东西都已经搜索过了,这是它的数值就不会发生变化,就可以入队了。这样保证了队列里的所有数值都不会发生变化。

#include<bits/stdc++.h>
using namespace std;
int n,m,ru[5005],chu[5005],a,b,f[5005],ans;
int mp[5005][5005];
queue<int> q;
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		scanf("%d%d", &a, &b);
		mp[a][b]=1;//记录关系
		chu[a]++;
		ru[b]++;//记录入度和出度
	}
	for(int i=1;i<=n;i++){
		if(ru[i]==0) {
			f[i]=1;
			q.push(i);//入度为零的入队
		}
	}
	while(!q.empty()){//队列不为空
		int a=q.front();
		q.pop();//出队
		for(int k=1;k<=n;k++){
			if(mp[a][k]==0)continue;
			f[k]+=f[a];//更新
			f[k]%=80112002;
			ru[k]--;//食物少了一个
			if(ru[k]==0){//入队为零才入队
				if(chu[k]==0){
					ans+=f[k];
					ans%=80112002;
                    continue;//有没有都行
				}
				q.push(k);
			}
		}
	}
	cout<<ans; 
}

简单来说,因为任务可以并发,所以一个任务如果有前驱的话,最优方案便是在它的最晚一个前驱结束后就立即开始,而且任务k的前驱节点一定小于k,所以读入时顺便从它的前驱里挑一个最大的转移即可。同时可以更新最终答案。

我的一些话

  • 今天给大家复习一下这几天都在学习的图论算法,关于图的遍历确实有一定难度,需要通盘的考虑和理解,以及扎实的数据结构基础才能独立写出AC代码。但无论难易,大家都要持续做题,保持题感喔!一起坚持(o′ω`o)

  • 如果有非计算机专业的uu自学的话,关于数据结构的网课推荐看b站上青岛大学王卓老师的课,讲的很细致,有不懂都可以私信我喔

  • 总结来说思路很重要,多想想,多在草稿纸上画画,用测试数据多调试,debug后成功编译并运行出正确结果真的会感到很幸福!

  • 关于之前蓝桥杯备赛的路线和基本方法、要掌握的知识,之前的博文我都有写,欢迎大家关注我,翻阅自取哦~

  • 不管什么都要坚持吧,三天打鱼两天晒网无法形成肌肉记忆和做题思维,该思考的时候一定不要懈怠,今天就说这么多啦,欢迎评论留言,一起成长:)

文章来源:https://blog.csdn.net/m0_73246124/article/details/135710873
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。