隐藏
「bsoj1453」食物链 - 树形动规 | Bill Yang's Blog
0%

「bsoj1453」食物链 - 树形动规

题目大意

    PCY 最近在努力地学习生物。看到食物链这一节的时候,他迷茫了。
    生态系统中的生物种类众多,亦于生态系统分别扮演着不同的角色,但根据它们在能量和物质中所引起的作用,可以被分类为生产者、消费者和分解者三个类别。最底层是“生产者”,是以阳光来行使光合作用,自行用水和二氧化碳等无机物合成有机物的绿色植物;再上层是各级“消费者”,要依赖生产者供应物质和能量;当消费者死亡以后,“分解者”会以他们的尸体为食物。
    生物必修二曾写道,“两个营养级之间的能量传递效率为$10\%\rightarrow20\%$”。
    PCY说,“那些错综复杂的食物网我根本看不清楚”,于是我们将问题简化,每一个物种只存在唯一一个的捕食者(形成捕食关系),给出这些捕食关系,和每个物种所拥有的能量。求出整个食物网中食物链的数量和处在最高营养级的物种的能量。(某一物种的能量=摄入食物的能量*传递效率+自身能量),不考虑能量损耗,为了避免精度误差,能量效率按均为整数计算。也就是说,一个物种被吃了以后他的能量就成了他的数倍了。


题目分析

简单的树形动规,需要注意手工栈+卡常数。


代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
namespace FastIO {
const int L=1<<15;
char buf[L],*S,*T;
char getchar() {
if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
return *S++;
}
LL Get_Int(){
LL res=0,bj=1;char c=getchar();
while(!isdigit(c)){if(c=='-')bj=-1;c=getchar();}
while(isdigit(c)){res=res*10+c-'0';c=getchar();}
return res*bj;
}
}
using FastIO::Get_Int;
const int maxn=2000005;
const LL mod=32416190071;
int n,vst[maxn],ans=0;
LL f[maxn];
struct Edge {
int from,to,dist;
};
vector<Edge>edges[maxn];
void AddEdge(int x,int y,int v) {
edges[x].push_back((Edge) {
x,y,v
});
}
void Dfs(int Now) {
for(auto& e:edges[Now]) {
int Next=e.to;
Dfs(Next);
f[Now]=(f[Now]+f[Next]*e.dist)%mod;
}
}
int main() {
int size=100<<20; //40M
__asm__ ("movq %0,%%rsp\n"::"r"((char*)malloc(size)+size));
n=Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int(),v=Get_Int();
vst[y]=1;
AddEdge(x,y,v);
}
int root;
for(int i=1; i<=n; i++) {
f[i]=Get_Int()%mod;
if(!edges[i].size())ans++;
if(!vst[i])root=i;
}
Dfs(root);
printf("%d\n%lld\n",ans,f[root]);
exit(0);
}
姥爷们赏瓶冰阔落吧~