P4017 最大食物链计数

2023-11-05 15:35| 来源: 网络整理| 查看: 265

最大食物链计数

洛谷题目 p4017

题目重述

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

题目描述给你一个食物网，你要求出这个食物网中最大食物链的数量。

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

Delia 非常急，所以你只有 11 秒的时间。

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

输入格式第一行，两个正整数 n、mn、m，表示生物种类 nn 和吃与被吃的关系数 mm。

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

输出格式一行一个整数，为最大食物链数量模上 80112002 的结果。

解题思路

解题思路详情见参考资料1这里写的很清楚，他的做法更巧妙，我的做法其实反而更笨拙，消耗空间也大，但个人感觉二维数组更容易理解。

拓扑排序法

通过邻接矩阵dist保存节点连线，如果存在有向边i->j 则令dist[i][j] = 1设置IN数组标记每个点的入度flage数组标记是否已经被处理过了首先初始化IN数组确定每个数组的入度，并将flage置为0，将不存在入度的点（生产者）记录为ways[i]=1，方便后续处理 for(ll i=1;i if(IN[i]==0 && flage[i]==0){ flage[i] = 1; break; } } // 去点操作 for(ll j=1;j IN[j] -= 1; ways[j] += ways[i]; ways[j] = ways[j] % mod; } } 只要将所有的空点都寻找干净了，就结束最终代码实现 #include using namespace std; const long long M = 2500000; const int MAX = 5001; // 最多的节点个数 const long long int mod = 80112002; // 12397542091227 typedef long long int ll; // 定义数据 ll n,m; int dist[MAX][MAX]; // 路径矩阵 int ISOUT[M]; // 是否存在出度 int IN[M]; // 入度记录向量 int flage[M]; // 是否处理过（标记向量） int ways[M]; // 路径数量 // 我感觉这个有点类似之前那个卒过河问题只不过这个路径是我们自己设置的 int main(){ memset(ISOUT, 0, sizeof(ll) * MAX); memset(IN, 0, sizeof(ll) * MAX); memset(flage, 0, sizeof(ll) * MAX); // 0表示未标记 1表示已经标记 cin >> n >> m; // 物种种类,捕食关系i->j ll a ,b; for(ll i=1;i if(IN[i]==0 && flage[i]==0){ ways[i] = 1; } } // 开始迭代计算 while(1){ // 寻找空点位置 ll i=1; for(i=1;i flage[i] = 1; break; } } // 去点操作 for(ll j=1;j IN[j] -= 1; ways[j] += ways[i]; ways[j] = ways[j] % mod; } } // 跳出循环的条件 if(i>n){ break; } } /* for(int i=1;i

【本文地址】

公司简介

联系我们