P318javascript:void(‘FE2C24‘)3 [HAOI2016] 食物链（记忆化搜索）-Toy模板网

这篇具有很好参考价值的文章主要介绍了P318javascript:void(‘FE2C24‘)3 [HAOI2016] 食物链（记忆化搜索）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1:思路：

从入读为零的点进行记忆化搜索，搜到出度为零的点返回1，所有返回值加起来就是答案。

int dfs(int u){
	if(f[u]!=-1) return f[u];//记忆化搜索 
	int res=0;
	if(chu[u]==0) return 1;//到达食物链底端 
	for(auto to:v[u]){
	res+=dfs(to);
	}
	f[u]=res;//*记忆 
	return res;
}

2:“注意单独的一种孤立生物不算一条食物链。”出题人都这么好心的说了，然而第一次交的时候还是忘了= =（不然只有20分）

  for(int i=1;i<=n;i++){
  	if(ru[i]==0&&chu[i]!=0) //食物链顶端 ,(食物链顶端的同时要满足不是底端） 
	  //即：注意单独的一种孤立生物不算一条食物链。
	  q.push(i);
  }

3:ACcode:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
vector<int>v[N];
int f[N],n,m,ru[N],chu[N],ans;
queue<int>q;
int dfs(int u){
	if(f[u]!=-1) return f[u];//记忆化搜索 
	int res=0;
	if(chu[u]==0) return 1;//到达食物链底端 
	for(auto to:v[u]){
	res+=dfs(to);
	}
	f[u]=res;//*记忆 
	return res;
}
void solve() {
  cin>>n>>m;
  for(int i=1;i<=m;i++){
  	int a,b;
  	cin>>a>>b;//被吃，吃 
  	v[b].push_back(a);
  	ru[a]++; 
  	chu[b]++;
  }
  for(int i=1;i<=n;i++){
  	if(ru[i]==0&&chu[i]!=0) //食物链顶端 ,(食物链顶端的同时要满足不是底端） 
	  //即：注意单独的一种孤立生物不算一条食物链。
	  q.push(i);
  }
  memset(f,-1,sizeof f); 
  while(!q.empty()){
  	dfs(q.front());
  	ans+=f[q.front()];
  	q.pop();
  }
  cout<<ans<<"\n";
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int tt=1;
	//cin>>tt;
	while(tt--)
		solve();
	return 0;
}

over~bb文章来源地址https://www.toymoban.com/news/detail-615556.html

到了这里，关于P318javascript:void(‘FE2C24‘)3 [HAOI2016] 食物链（记忆化搜索）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！