题解 P4017 【最大食物链计数】
__Watcher
·
·
题解
好久没写题解了，在这里水一波
update 2019.11.15 优化代码风格，增加正确性证明&注释
update 2020.1.6 使题解满足新版规定
update 2020.6.26 再次更新
update 2024.1.6 再次更新使题解满足规定
总的思路：拓扑排序 （管理员别以为我的题解和楼下的一样）
这里具体讲一下为什么要用拓扑排序（思维过程）：
1、这是一道图论题；
2、不是求最短路；
3、根据提示“最左端是不会捕食其他生物的生产者”可以想到，我们要入度为零的点开始查找；
4、再看一遍题目，就是求路径数，当且仅当一个点的入度变为零时才需要入队，并不是数据更新一次就要入队；
5、出度为零的点的路径总数和就是答案。
思路已经呼之欲出了：拓扑排序！
下面讲讲如何实现。
拓扑排序的精髓就在于每个点只会入队一次，每条边只会通过一次，所以时间复杂度就有很好的保证，O(N+M)，SPFA 的玄学时间复杂度）。
正确性说明：题目的补充说明告诉我们这是一张 DAG（有向无环图），因此必定存在一个入度为 0 的点，也因此每一个点都会被遍历。
下面的代码的变量解释：
$h_i$ 表示在可以直接吃掉 $i$ 的所有关系中最后的一条的编号（邻接矩阵用）；
$ru_i$ 表示 $i$ 的入度，是整个程序的核心数组；
$mp_{i,j}$ 表示 $j$ 是否能直接吃掉 $i$；
$chu_i$ 表示 $i$ 的出度；
结构体 AB 记录 $m$ 条关系。
当一个点的入度变为零，即所有它能吃的东西都已经搜索过了，这是它的数值就不会发生变化，就可以入队了。这样保证了队列里的所有数值都不会发生变化。
---
实现方式有以下两种：
方法一：
观察到数据范围 $n \le 5000$，用计算器一摁，发现不会 MLE ，于是就可以大胆地开一个二维数组（即邻接矩阵）存储吃与被吃的关系。代码如下：
```cpp
#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;
}
```
实测时空规模：598ms / 94.18MB （在 MLE 的边缘疯狂试探）
方法二：
用邻接表存储吃与被吃的关系，其他的和上一个代码几乎一模一样。代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int mod=80112002;
int n, m, h[5005], ru[5005], chu[5005], f[5005], ans;
struct AB{
int a,b,n;
}d[5000005];
queue<int> q;
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int a, b;
scanf("%d%d", &a, &b);
d[i].a=a, d[i].b=b, d[i].n=h[a], h[a]=i;//建图
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=h[a];k;k=d[k].n){
int b=d[k].b;
f[b]+=f[a];
f[b]%=mod;
ru[b]--;
if(ru[b]==0){
if(chu[b]==0){
ans+=f[b];
ans%=mod;
}//出度为0的点为食物链终点，记录答案，并且不必入队
else q.push(b);
}
}
}
cout<<ans;
}
```
实测时空规模： 225ms / 7.70MB
多说几句：优化方法：
1、开O2优化 204ms / 6.65MB
2、读入优化 111ms / 7.01MB
3、膜拜AK IOI的巨佬 请亲测