国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > bzoj4562【HAOI2016】食物链

bzoj4562【HAOI2016】食物链

来源:程序员人生   发布时间:2016-08-24 08:34:17 阅读次数:2510次

4562: [Haoi2016]食品链

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 216  Solved: 173
[Submit][Status][Discuss]

Description

如图所示为某生态系统的食品网示意图,据图回答第1小题
现在给你n个物种和m条能量活动关系,求其中的食品链条数。
物种的名称为从1到n编号
M条能量活动关系形如
a1 b1
a2 b2
a3 b3
......
am⑴ bm⑴
am bm
其中ai bi表示能量从物种ai流向物种bi,注意单独的1种孤立生物不算1条食品链

Input

第1行两个整数n和m,接下来m行每行两个整数ai bi描写m条能量活动关系。
(数据保证输入数据符号生物学特点,且不会有重复的能量活动关系出现)
1<=N<=100000 0<=m<=200000
题目保证答案不会爆 int

Output

1个整数即食品网中的食品链条数

Sample Input

10 16
1 2
1 4
1 10
2 3
2 5
4 3
4 5
4 8
6 5
7 6
7 9
8 5
9 8
10 6
10 7
10 9

Sample Output

9



DP水题




#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #define F(i,j,n) for(int i=j;i<=n;i++) #define D(i,j,n) for(int i=j;i>=n;i--) #define ll long long #define N 100005 using namespace std; int n,m,cnt,ans,f[N],head[N],in[N]; bool tag[N]; struct edge{int next,to;}e[N*2]; inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=⑴;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void add_edge(int x,int y){e[++cnt]=(edge){head[x],y};head[x]=cnt;} void dfs(int x) { for(int i=head[x];i;i=e[i].next) { int y=e[i].to; f[y]+=f[x];in[y]--; if (!in[y]) dfs(y); } } int main() { n=read();m=read(); F(i,1,m){int x=read(),y=read();add_edge(x,y);in[y]++;} F(i,1,n) tag[i]=!in[i]&&head[i]; F(i,1,n) if (tag[i]) f[i]=1,dfs(i); F(i,1,n) if (!head[i]) ans+=f[i]; printf("%d\n",ans); return 0; }


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生