HAOI2016

问题叙述

微生物 1

如图所示为某某生态系统的食物网示意图,据图对第1有些题现在为你n个物种与m条能量流动涉及,求中的食品链条数。物种的名号为打1交n编号M条能量流动涉及形如a1
b1a2 b2a3 b3……am-1 bm-1am bm其中ai
bi表示能从物种ai流向物种bi,注意单独的同样种孤立生物不算是一长长的食物链

输入输出格式

输入格式:

 

第一履两独整数n和m,接下m行每行两单整数ai
bi描述m条能量流动涉及。(数据保证输入数据符号生物学特性,且无会见有重的能流动涉及起)1<=N<=100000
0<=m<=200000题材保证答案不会见爆 int

 

出口格式:

 

一个整数即食物网中之食品链条数

 

输入输出样例

输入样例#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

题目标签写的是动态规划,但是自己yy了一种拓扑排序+出入度统计的做法,第一遍交居然A了,,
做法很简单,
记两个入度数组,一个用作拓扑排序,一个用作判断答案,然后记一个出度,
拓扑排序
最后特判一下加个和就好

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<queue>
 6 using namespace std;
 7 const int MAXN=400001;
 8 inline void read(int &n)
 9 {
10     char c=getchar();n=0;bool flag=0;
11     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();
12     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
13 }
14 struct node
15 {
16     int u,v,w,nxt;
17 }edge[MAXN];
18 int head[MAXN];
19 int num=1;
20 int dp[MAXN];
21 int chudu[MAXN];
22 int rudu2[MAXN];
23 inline void add_edge(int x,int y,int z)
24 {
25     edge[num].u=x;
26     edge[num].v=y;
27     edge[num].w=z;
28     edge[num].nxt=head[x];
29     head[x]=num++;
30 }
31 int rudu[MAXN];
32 int n,m;
33 void Topsort()
34 {
35     queue<int>q;
36     int tot=0;
37     for(int i=1;i<=n;i++)
38         if(!rudu[i])    q.push(i),tot++;
39     while(q.size()!=0)
40     {
41         int p=q.front();
42         q.pop();
43         for(int i=head[p];i!=-1;i=edge[i].nxt)
44         {
45             dp[edge[i].v]+=dp[p];
46             rudu[edge[i].v]--;
47             if(!rudu[edge[i].v]    )    q.push(edge[i].v);
48         }
49     }
50 }
51 int main()
52 {
53     memset(head,-1,sizeof(head));
54     read(n);read(m);
55     for(int i=1;i<=m;i++)
56     {
57         int a,b;read(a);read(b);
58         add_edge(a,b,1);
59         rudu[b]++;
60         rudu2[b]++;
61         chudu[a]++;
62     }
63     for(int i=1;i<=n;i++)
64         if(!rudu[i])    dp[i]=1;
65     Topsort();
66     int ans=0;
67     for(int i=1;i<=n;i++)
68         if(chudu[i]==0&&rudu2[i]!=0)
69             ans+=dp[i];
70     printf("%d",ans);
71     return 0;
72 }

微生物, 

 

相关文章