最大食物链计数

洛谷题目 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<=m;i++){ cin >> a >> b; dist[a][b] = 1; // 输入位置记录 IN[b] += 1; ISOUT[a] = 1; // 存在出度的就不是 顶级捕食者 } 每次都从入度为0的节点开始拆分，也就是寻找IN[i]==0 && flage[i]==0的位置，确定第i个节点，查找第i个节点入度点j，将这些节点对应位置的ways数组点加上对应的值也就是 // 寻找空点位置 ll i=1; for(i=1;i<=n;i++){ if(IN[i]==0 && flage[i]==0){ flage[i] = 1; break; } } // 去点操作 for(ll j=1;j<=n;j++){ if(dist[i][j] == 1){ IN[j] -= 1; ways[j] += ways[i]; ways[j] = ways[j] % mod; } } 只要将所有的空点都寻找干净了，就结束

最终代码实现

#include<bits/stdc++.h> 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<=m;i++){ cin >> a >> b; dist[a][b] = 1; // 输入位置记录 IN[b] += 1; ISOUT[a] = 1; // 存在出度的就不是 顶级捕食者 } // 查找最起始的生产者 for(ll i=1;i<=n;i++){ if(IN[i]==0 && flage[i]==0){ ways[i] = 1; } } // 开始迭代计算 while(1){ // 寻找空点位置 ll i=1; for(i=1;i<=n;i++){ if(IN[i]==0 && flage[i]==0){ flage[i] = 1; break; } } // 去点操作 for(ll j=1;j<=n;j++){ if(dist[i][j] == 1){ IN[j] -= 1; ways[j] += ways[i]; ways[j] = ways[j] % mod; } } // 跳出循环的条件 if(i>n){ break; } } /* for(int i=1;i<=n;i++){ cout << ways[i] << " "; cout << ISOUT[i] << " "; } */ ll sum = 0; for(int i=1;i<=n;i++){ sum = sum + ways[i]*!ISOUT[i]; sum = sum % mod; } cout << sum; return 0; }

一些问题

之前用了longlong声明的二维数组，结果MLE了，这次改成int可以了。这个方法是疯狂的以空间换时间，但是还是很笨拙。

参考资料

洛谷_P4017 最大食物链计数 （尚贤）关于dp和记忆化搜索取舍