大雪菜味题解--P4017 最大食物链计数

P4017最大食物链计数

标签：图论、拓扑排序

思路：首先我们要理解题目，我因为看错题浪费了我好几个小时，我本来以为求的是这个食物链网里面那一条食物链最长，长度是多少，然后我就直接按照–进阶指南-可达性统计（链接）这题的思路来做了，直接浪费了很长时间。这道题的意思是求这个食物链网中有多少条食物链，一条完整的食物链的开头入度为0，结尾肯定是出度为0，这样就认为是一条食物链，对了，同时注意！！！，这里边的数量有500000条所以这里不能用邻接表来存，要用邻接矩阵来存。基本步骤是：

1. 建立邻接矩阵存储图、边，记录下来每一个点的出度和入度
2. 求这张有向无环图的拓扑序列
3. 依次遍历拓扑序列的每一个点并累加点的食物链数
4. 枚举出度为0的点，并ans+=此点的食物链数

这里具体讲一下为什么要用拓扑排序（思维过程）：（摘自洛谷题解区@_Watcher ）
1、这是一道图论题；
2、不是求最短路；
3、根据提示“最左端是不会捕食其他生物的生产者”可以想到，我们要入度为零的点开始查找；
4、再看一遍题目，就是求路径数，当且仅当一个点的入度变为零时才需要入队，并不是数据更新一次就要入队；
5、出度为零的点的路径总数和就是答案。
思路已经呼之欲出了：拓扑排序
拓扑排序的精髓就在于每个点只会入队一次，每条边只会通过一次，所以时间复杂度就有很好的保证

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;

const int N=5010,mod=80112002;

vector<int> g[N];  //用邻接矩阵来存图
int d[N],p[N],num[N];  //d表示入度，p表示出度,num[i]记录到这个点的食物链的数量
int n,m;
LL ans=0;


void topsort(){
    
	queue<int> q;
	for(int i=1;i<=n;i++){
    
		if(d[i]==0){
    
			// cout<<"入度为0："<<i<<endl;
			num[i]=1;
			q.push(i);
		}
	}
	int k=0;
	while(!q.empty()){
    
		auto t=q.front();
		q.pop();
		
		for(auto j:g[t]){
    
			d[j]--;
			num[j]=(num[j]+num[t])%mod;  //更新j点的食物链数
			if(d[j]==0){
    
				q.push(j);
			}
		}
	}
	
}

int main(){
    
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin>>n>>m;

	for(int i=0;i<m;i++){
    
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		d[b]++;
		p[a]++;
	}
	
	topsort();
	
    for(int i=1;i<=n;i++){
    
		if(p[i]==0){
    
			ans=(ans+num[i])%mod;
		}
	}
	
	cout<<ans;
	
	return 0;
}

@本人不太会表达，算法也只是初窥门径，如果有什么看不懂，写的不好的地方，欢迎在评论区留言，我会吸取教训，慢慢完善自己，谢谢！