首页 > > 程序设计 > C/C++ >

P3183 [HAOI2016]食物链

2018-06-17 21:52:59来源：未知阅读 ()

题目描述

如图所示为某生态系统的食物网示意图，据图回答第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 }