首页 > 其他分享 >P4017 最大食物链计数

P4017 最大食物链计数

时间:2023-11-29 14:34:05浏览次数:41  
标签:食物链 head int ++ cnt 计数 edge include P4017

P4017 最大食物链计数

记忆化搜索 DP 角度解

  • 从捕食者向被捕食者建边
  • 维护每个生物的捕食 eat,和被捕食数量 beat
  • 对每一个食物链顶端 dfs,向下搜索直到找到最低级的生物,记忆化当前结点对应的食物链长度。
#include <iostream>
#include <algorithm>
#include <cstring>

#define mod %80112002

using namespace std;

const int N = 5e3 + 5;
const int M = 5e5 + 5;

struct Node{
	int to, next;
}edge[M];
int head[N];
int cnt = 0;
int n, m;
int ans;
int eat[N], beat[N], F[N];

void addEdge(int a, int b)
{
	edge[cnt].to = b;
	edge[cnt].next = head[a];
	head[a] = cnt++;
}

void preProcessing()
{
	memset(head, -1 , sizeof(head));
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int a, b;
		cin >> a >> b;
		addEdge(b, a);
		eat[b]++;
		beat[a]++; 
	}
}

int dfs(int u)
{
	int sum = 0;
	if (!eat[u])
	{
		return 1;
	}
	if (F[u])
	{
		return F[u];	
	} 
	for (int j = head[u]; j != -1; j = edge[j].next)
	{
		sum = (sum + dfs(edge[j].to)) mod;
	}
	return F[u] = sum;
}

int main()
{
	preProcessing();
	for (int i = 1; i <= n; i++)
	{
		if (!beat[i])
		{
			ans += dfs(i);
			ans = ans mod;
		}
	}
	cout << ans;
	return 0;
}

拓扑排序角度解

  • 从被捕食者向捕食者建边
  • 维护每个生物(结点)的入度 ind,和出度 otd
  • 直接对整个食物网拓扑排序,排序的过程中自然维护一个 num 数组表示到当前结点的最长链。
  • 求和出度为 \(0\) 的 num 数组即可。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

#define mod %80112002

using namespace std;

const int N = 5e3 + 5;
const int M = 5e5 + 5;

struct Node{
	int to, next;
}edge[M];
int head[N];
int cnt = 0;
int n, m;
int ans;
int ind[N], otd[N], F[N], num[N];

void addEdge(int a, int b)
{
	edge[cnt].to = b;
	edge[cnt].next = head[a];
	head[a] = cnt++;
}

void preProcessing()
{
	memset(head, -1 , sizeof(head));
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int a, b;
		cin >> a >> b;
		addEdge(a, b);
		ind[b]++;
		otd[a]++; 
	}
}

void bfs()
{
	queue<int> q;
	for (int i = 1; i <= n; i++) 
	{
		if (!ind[i]) num[i] = 1, q.push(i);
	}
	while(!q.empty())
	{
		int f = q.front();
		q.pop();
		for (int i = head[f]; i != -1; i = edge[i].next)
		{
			int t = edge[i].to;
			--ind[t];
			num[t] = (num[t] + num[f]) mod;
			if (ind[t] == 0) q.push(t);
		}
	}
}

int main()
{
	preProcessing();
	bfs();
	for (int i = 1; i <= n; i++)
	{
		if (!otd[i])
		{
			ans = (ans + num[i]) mod;
			ans = ans mod;
		}
	}
	cout << ans;
	return 0;
}

标签:食物链,head,int,++,cnt,计数,edge,include,P4017
From: https://www.cnblogs.com/kdlyh/p/17864768.html

相关文章

  • 计数比较模块(CC)与动作模块
    1.4计数比较模块CC1.计数比较模块的作用图10ePWM计数比较模块原理框图计数比较模块以时基计数器的值作为输入,与比较寄存器CMPA和比较寄存器CMPB不断进行比较,当时基计数器的值等于其中之一时,就会产生相应的事件。①产生比较事件具体取决于编程时是采用寄存器A还是寄存器B:--CTR=CMP......
  • 不常见的排序算法 - 桶排序、计数排序、基数排序
    提到排序,我们最先想到的肯定是常见的那些排序算法:选择排序、冒泡排序、快速排序、归并排序考虑到性能的情况下,我们应该会优先使用快速排序,因为它的平均时间复杂度是O(nlogn),至于归并排序,虽然它也是一个拥有O(nlogn)平均时间复杂的一个算法,但是它的空间复杂度较快排也较为苛刻,它......
  • ACM中的组合计数题单好题汇总(持续更新中)
    前言:这里会分享一些精妙的组合计数题,此类题往往需要选择合适的计数集合的划分方式,有些计数角度的精妙,个人感觉没有做过相对的题目,或者是计数感足够犀利,实在是很难想到正确的角度,所以这里会汇总一些有趣的计数题,希望可以帮助到一部分人ARC168C-SwapCharacte......
  • 计数的思想
    计数的思想,源自于计数排序。计数就是把出现过的元素个数进行记录。在集合相关操作中,计数+1表示加入元素,计数-1表示删除元素。我们在操作过程中,有时要对某些变量进行记录,记录出现的位置,记录上一次的值都是计数的思想。   本题我们采用计数的思想,记录每个字母出现的次数。s......
  • FPGA入门笔记004——BCD计数器设计与使用
    1、设置一个最大值为10的四位计数器,Verilog代码如下:moduleBCD_Counter( Clk, Cin, Rst_n, Cout, q); inputClk; //计数器基准时钟 inputCin; //计数器进位输入 inputRst_n; //系统复位 // outputRegCout; //计数器进位输出 outputCout; //计数器进位输出 out......
  • LY1464 [ 20231112 NOIP 模拟赛 T4 ] 序列计数
    题意给定\(n,m\)。求:\(a_1+a_2+...+a_m=n\)\(1^{a_1}\times2^{a_2}\times...\timesm^{a_m}\equivx(\bmodm)\)对于\(x\in[1,m)\)满足上述条件的方案数。Sol注意到下面的式子等价于:\(1\times1\times1...\times2\times2...\time......
  • FPGA入门笔记003——计数器IP核调用与验证
    FPGA设计方式主要有三种:1、原理图(不推荐);2、VerilogHDL设计方式;3、IP核输入方式计数器IP核调用与验证步骤如下:1、添加IP核文件打开QuartusII,新建一个项目,名称为counter_ip。选择Tools->MegaWizardPlug-InManager。选择第一个选项。在搜索栏中输入COUNTER,单击LPM_COU......
  • Java学习—计数排序
    计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。1.计数排序的特征当输入的元素是n个0到k之间的整数时,它的运行时间是Θ(n+k)。计数排序不是比较排序,排序的速度快于任......
  • T399753 counting problem(计数问题)题解
    LinkT399753countingproblem(计数问题)Question给出一个正整数\(n\),求\(AB+CD=n\)的方案数,\(A,B,C,D\)都是要求是正整数Solution考虑直接枚举\(ABCD\)显然是不切实际的那么就折半枚举设\(F_i\)表示两个数的乘积为\(i\)的方案数答案就是\(\sum\limits_{i=1......
  • 51定时计数器
        ......