HAOI2016食物链 题解

题目链接

题目给了这样的一张图作为例子。

题目只是要求计算食物链的条数,并没有要求找到每一条具体是什么。

观察一下食物链的特点:

  1. 有向
  2. 没有重边
  3. 没有环

我们可以通过递推来快速计算出食物链的条数。

先用个简单点的食物网举个例子。讲一下怎么推。

对于任意食物网,那么令起点S的值1,其他点的值为通向该点的所有点值之和。最后推得终点T的值就是食物链条数。

只有一条食物链时候,如图

增加一条食物链

再多一条

捕食关系稍微复杂一点也没有关系

只要严格按照递推关系,即使是复杂的食物网,都是可以推出来的。

那么,假如有多个起点和终点呢?

也没有关系的,还是严格按照规则,起点值为1,其他点的值是通向该点的所有点值和,总能推导终点的。

所有终点的值和就是食物链条数。

上图有5+6=11条食物链。

应用于题目给定的样例:

得到食物链条数为7+2=9条。

以上方法是可以直接应用在做生物题的。

下面说算法。

这种明显的地推关系,很显然记忆化搜索DP一下就可以了。

很显然递归操作,直接记忆化搜索:

1
2
3
4
5
6
7
8
9
10
11
# python胡写的伪代码
def DFS(point): #记忆化搜索
if visited[point]==True : #访问过的点
return DP[point]
visited[point]=True #打标记
if out[point]==0 : #终点
DP[point]=1
return 1
for Edge in EdgeList[point] :
DP[point]+=DFS(Edge.to) #累加点值
return DP[point]

递归操作无法实现从前往后递推,只能利用返回值从后往前着回溯来推。

直接在图上从起点递归,递归到终点,令终点值为1并返回。

回溯到上一个点,累加返回值,并继续向下搜索。

遇到已经计算过的点,直接返回计算好的该点的值就可以了。

遍历当前点连接的每一个点。

最后回溯到起点,累加返回值。

对于每一个起点都要搜一次。搜索结束的结果如图。

很显然,食物链的条数就是起点得到的值之和(7+4=11)。

只要从每一个入度为0的点搜一遍求和就是答案了。

还要注意一些细节,单个点不是食物链。入度和出度都为0的点能被算进去。(一开始就这么做了,然后20分……)

给出AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>
#include<cstdio>
#include<cstring>

using LL=long long;

const int inf=0x7fffffff;
const LL linf=0x7fffffffffffffff;

typedef struct EdgeNode
{
int to;
EdgeNode *next;
EdgeNode(int to,EdgeNode *nxt):to(to)
{
next=nxt;
}
~EdgeNode()
{
if(next!=nullptr)
delete next;
}
}*Edge;

struct Point
{
Edge head;
int eat;

Point()
{
head=nullptr;
eat=0;
}
~Point()
{
if(head!=nullptr)
delete head;
}

void eaten(int to)
{
head=new EdgeNode(to,head);
}
}*animal;

int n,m,*dp;
bool *vis;

int dfs(int pos)
{
if(vis[pos])//已经计算过的点
return dp[pos];
vis[pos]=true;//标记当前点
if(animal[pos].head==nullptr)//终点
return dp[pos]=1;
for(Edge node=animal[pos].head;node!=nullptr;node=node->next)
dp[pos]+=dfs(node->to);//累加点值
return dp[pos];
}

int main()
{
scanf("%d%d",&n,&m);
animal=new Point[n+1];
dp=new int[n+1];
vis=new bool[n+1];
memset(dp,0,(n+1)*sizeof(int));
memset(vis,0,(n+1)*sizeof(bool));
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
animal[u].eaten(v);
animal[v].eat++;
}
int ans=0;
for(int i=1;i<=n;i++)
if(!animal[i].eat && animal[i].head!=nullptr) //注意判断单个点
ans+=dfs(i);
printf("%d\n",ans);
delete [] animal;
delete [] dp;
delete [] vis;
return 0;
}