題目描述

如圖所示為某生態(tài)系統(tǒng)的食物網(wǎng)示意圖，據(jù)圖回答第1小題現(xiàn)在給你n個(gè)物種和m條能量流動(dòng)關(guān)系，求其中的食物鏈條數(shù)。物種的名稱(chēng)為從1到n編號(hào)M條能量流動(dòng)關(guān)系形如a1 b1a2 b2a3 b3......am-1 bm-1am bm其中ai bi表示能量從物種ai流向物種bi,注意單獨(dú)的一種孤立生物不算一條食物鏈

輸入輸出格式

輸入格式：

?

第一行兩個(gè)整數(shù)n和m,接下來(lái)m行每行兩個(gè)整數(shù)ai bi描述m條能量流動(dòng)關(guān)系。（數(shù)據(jù)保證輸入數(shù)據(jù)符號(hào)生物學(xué)特點(diǎn)，且不會(huì)有重復(fù)的能量流動(dòng)關(guān)系出現(xiàn)）1<=N<=100000 0<=m<=200000題目保證答案不會(huì)爆 int

?

輸出格式：

?

一個(gè)整數(shù)即食物網(wǎng)中的食物鏈條數(shù)

?

輸入輸出樣例

輸入樣例#1：
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 輸出樣例#1：
9

記憶化搜索?

屠龍寶刀點(diǎn)擊就送

#include <cstdio> #define Max 200000 struct node {int next,to; }edge[Max<<1]; int f[Max],cd[Max],rd[Max],ans,head[Max<<1],cnt,n,m; void add(int u,int v) {cnt++;edge[cnt].next=head[u];edge[cnt].to=v;head[u]=cnt; } int dfs(int x) {if(f[x]) return f[x];if(cd[x]==0) return 1;int k=0;for(int i=head[x];i;i=edge[i].next) k+=dfs(edge[i].to);f[x]=k;return k; } int main() {scanf("%d%d",&n,&m);for(int x,y;m--;){scanf("%d%d",&x,&y);cd[x]++;rd[y]++;add(x,y);}for(int i=1;i<=n;++i){if(rd[i]==0&&cd[i]!=0)ans+=dfs(i);}printf("%d",ans);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/ruojisun/p/6680000.html

總結(jié)

以上是生活随笔為你收集整理的洛谷 P3183 [HAOI2016]食物链的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。