网站技术制作,微信网站开发 js框架,大连的网站设计公司电话,四川华泰建设集团网站题目描述 如图所示为某生态系统的食物网示意图#xff0c;据图回答第1小题现在给你n个物种和m条能量流动关系#xff0c;求其中的食物链条数。物种的名称为从1到n编号M条能量流动关系形如a1 b1a2 b2a3 b3......am-1 bm-1am bm其中ai bi表示能量从物种ai流向物种bi,注意单独的… 题目描述 如图所示为某生态系统的食物网示意图据图回答第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条能量流动关系。数据保证输入数据符号生物学特点且不会有重复的能量流动关系出现1N100000 0m200000题目保证答案不会爆 int 输出格式 一个整数即食物网中的食物链条数 lv神考试也不知道是Day几反正是T2然后T1是期望dp 上来看了一眼然后写了记忆化搜索毕竟没有什么思维难度 转移也很简单只要记录以每个点为终点的食物链数量然后将没有天地的生物的食物链数相加即可 简单到飞起 下面给出代码 }return f[x];
}
int main(){nrd();mrd();for(int i1;im;i){int x,y;xrd();yrd();add(y,x);book[x]1;vis[x];vis[y];}for(int i1;in;i) if(!book[i]vis[i]) ansfind(i,0);printf(%d,ans);return 0;
} 然后你以为结束了 不不不我发现机房除了我好像都是拓扑排序所以我打算用一波新操作 我们很明显的可以看出这是个DAG然后排序然后再来一个简单的转移 把后面的转给前面的因为是营养级高的先进队 其实是为了写博客才写的但是调了好久QAQ 下面给出代码因为不经常写拓扑所以比较丑 #includeiostream
#includecmath
#includecstdio
#includecstdlib
#includecstring
#includestring
#includealgorithm
using namespace std;
inline int rd(){int x0,f1;char cgetchar();for(;!isdigit(c);cgetchar()) if(c-) f-1;for(;isdigit(c);cgetchar()) xx*10c-0;return x*f;
}
inline void write(int x){if(x0) putchar(-),x-x;if(x9) write(x/10);putchar(x%100);
}
int n,m;
int head[1000006];
int nxt[1000006],to[1000006];
int total0;
int in[1000006];
void add(int x,int y){total;to[total]y;nxt[total]head[x];head[x]total;return ;
}
int q[1000006];
int book[1000006];
int tot0;
void topo(){for(int i1;in;i) if(!in[i]book[i]) q[tot]i;for(int i1;itot;i){for(int ehead[q[i]];e;enxt[e]){in[to[e]]--;if(!in[to[e]]) q[tot]to[e];}}return ;
}
int dp[1000006];
int in2[1000006];
int vis[1000006];
int x[1000006],y[1000006];
int main(){nrd(),mrd();for(int i1;im;i){x[i]rd();y[i]rd();add(x[i],y[i]);in[y[i]];in2[y[i]];vis[x[i]];book[x[i]];book[y[i]];}topo();int ans0;memset(head,0,sizeof(head));for(int i1;im;i) add(y[i],x[i]);for(int i1;itot;i){if(!in2[q[i]]) dp[q[i]]1;else for(int ehead[q[i]];e;enxt[e]) dp[q[i]]dp[to[e]];if(!vis[q[i]]) ansdp[q[i]];}printf(%d,ans);return 0;
} 转载于:https://www.cnblogs.com/WWHHTT/p/9726996.html
