[JZOJ5166] [NOIP2017模拟6.26卢学魔] 解题报告 (记忆化搜索|拓扑排序)
2024-10-01 13:37:29
题目链接:
http://172.16.0.132/senior/#main/show/5166
题目:
题解:
这个没什么好讲的,就是注意生产者没人吃也不是食物链,这告诉我们要积累生物知识注意细节
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
typedef long long ll; const int N=1e5+;
int n,m,tot;
int ru[N],head[N],chu[N];
ll dp[N];
queue <int> q;
struct EDGE
{
int to,nxt;
}edge[N<<];
inline int read()
{
char ch=getchar();
int s=,f=;
while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}
return s*f;
}
void add(int u,int v)
{
edge[++tot]=(EDGE){v,head[u]};
head[u]=tot;
}
int dfs(int x)
{
if (!chu[x])
{
dp[x]=;return dp[x];
}
for (int i=head[x];i;i=edge[i].nxt)
{
int y=edge[i].to;
if (!dp[y]) dp[y]=dfs(y);
dp[x]+=dp[y];
}
return dp[x];
}
int main()
{
n=read();m=read();
for (int i=,u,v;i<=m;i++)
{
u=read();v=read();
add(u,v);chu[u]++;ru[v]++;
}
for (int i=;i<=n;i++) if (!dp[i]) dfs(i);
ll ans=;
for (int i=;i<=n;i++) if (!ru[i]&&head[i]) ans+=dp[i];//head[i]不可以去掉,生产者没人吃也不是食物链
printf("%lld\n",ans);
return ;
}
最新文章
- JAVA安全模型
- .net 获取https页面的信息 在iis7.5服务器上不管用
- RHEL/CentOS/Fedora常用的 CentOS 5/6/7 yum 源(EPEL、Remi、RPMForge、RPMFusion, ius,163,sohu,阿里云)配置
- [51Testing情人节活动]情人节,爱要有“礼”才完美!
- Manacher算法----最长回文子串
- Go程序GC优化经验分享
- 使用SqlBulkCopy导入数据至MS SQL Server
- 详解Linux文档属性、拥有者、群组、权限、差异
- go chan 入门代码
- C# System.Guid.NewGuid() 格式化
- java多线程的3种写法
- JAVA 创建文件和文件夹,删除文件和文件夹的实用工具
- asp.net core部署时自定义监听端口,提高部署的灵活性
- Python 如何创建2维空数组
- odoo权限
- Linux下seq的使用
- ab的使用方法【转】
- Python学习笔记之函数参数传递 传值还是传引用
- 使用vigil 监控微服务系统包含可视化界面
- 001服务注册与发现Eureka