bzoj4562【HAOI2016】食物鏈
來源：程序員人生 發布時間：2016-08-24 08:34:17 閱讀次數：2688次
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
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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
